Все мы знаем, что вопрос P = NP поистине увлекателен, но сейчас его скоро выпустят в виде фильма. Могут ли они быть серьезными? Да, доказательство того, что P = NP изменит мир, каким мы его знаем.
Всегда приветствуются фильмы, посвященные науке и технологиям, но разве не часто у нас есть фильмы, посвященные информатике. «Коммивояжер» — такой уж редкий фильм. Как вы можете догадаться по названию, это проблема коммивояжера, а точнее вопрос P = NP. Автор сценария и режиссер Тимоти Ланзоне, а продюсер — Fretboard Pictures, премьера должна состояться 16 июня.
Это научная фантастика? Сложный вопрос, потому что он уходит корнями в современный мир кибератак и взломов. Идея состоит в том, что современная криптография зависит от идеи, что некоторые проблемы слишком сложно решить за разумное время, т.е. что NP — это не то же самое, что P.
Сюжет фильма основан на том, что произошло бы, если бы некий компьютерный ученый смог доказать, что NP = P. В таком случае все коды, основанные на задачах NP, в принципе, можно было бы взломать. Результатом этого может стать полная бесполезность всей криптографии с открытым ключом, поскольку проблемы NP, на которых она основана, могут быть преобразованы в проблемы в P и решены в «разумное» время.
Как говорится в аннотации к трейлеру фильма:
TRAVELING SALESMAN — это интеллектуальный триллер о четырех самых умных математиках мира, нанятых правительством США для решения самой неуловимой проблемы в истории информатики — P vs. NP. Эти четверо совместно создали «систему», которая может стать следующим крупным достижением человечества или крахом общества.
В то время как математики собираются подписать документы, которые предоставят правительству единоличную и частную собственность на их решение, они борются с моральной дилеммой относительно того, как будет использоваться их знаменательное открытие.
Вы можете начать видеть, что есть возможности для некоторой драмы, но вместо того, чтобы подробно объяснять, лучше просто посмотреть трейлер:
Похоже, это отличное развлечение, и его стоит посмотреть.
Однако, несмотря на то, что описание фильма заканчивается на
Математика настоящая. Последствия реальны.
что правда, ситуация намного сложнее.
Чтобы NP = P было открытием, изменившим мир, оно должно привести к полиномиальным решениям низкого порядка. Полиномиально масштабируемое решение бесполезно, если для фактического вычисления все еще требуется возраст Вселенной.
Это отличная история, и я надеюсь, что она настолько повысит осведомленность общественности о компьютерных науках, что станет интересным предметом для изучения.