Коммивояжер — Фильм про P = NP


Все мы знаем, что вопрос P = NP поистине увлекателен, но сейчас его скоро выпустят в виде фильма. Могут ли они быть серьезными? Да, доказательство того, что P = NP изменит мир, каким мы его знаем.

Всегда приветствуются фильмы, посвященные науке и технологиям, но разве не часто у нас есть фильмы, посвященные информатике. «Коммивояжер» — такой уж редкий фильм. Как вы можете догадаться по названию, это проблема коммивояжера, а точнее вопрос P = NP. Автор сценария и режиссер Тимоти Ланзоне, а продюсер — Fretboard Pictures, премьера должна состояться 16 июня.

Это научная фантастика? Сложный вопрос, потому что он уходит корнями в современный мир кибератак и взломов. Идея состоит в том, что современная криптография зависит от идеи, что некоторые проблемы слишком сложно решить за разумное время, т.е. что NP — это не то же самое, что P.

Сюжет фильма основан на том, что произошло бы, если бы некий компьютерный ученый смог доказать, что NP = P. В таком случае все коды, основанные на задачах NP, в принципе, можно было бы взломать. Результатом этого может стать полная бесполезность всей криптографии с открытым ключом, поскольку проблемы NP, на которых она основана, могут быть преобразованы в проблемы в P и решены в «разумное» время.

Как говорится в аннотации к трейлеру фильма:

TRAVELING SALESMAN — это интеллектуальный триллер о четырех самых умных математиках мира, нанятых правительством США для решения самой неуловимой проблемы в истории информатики — P vs. NP. Эти четверо совместно создали «систему», которая может стать следующим крупным достижением человечества или крахом общества.

В то время как математики собираются подписать документы, которые предоставят правительству единоличную и частную собственность на их решение, они борются с моральной дилеммой относительно того, как будет использоваться их знаменательное открытие.

Вы можете начать видеть, что есть возможности для некоторой драмы, но вместо того, чтобы подробно объяснять, лучше просто посмотреть трейлер:

Похоже, это отличное развлечение, и его стоит посмотреть.

Однако, несмотря на то, что описание фильма заканчивается на

Математика настоящая. Последствия реальны.

что правда, ситуация намного сложнее.

Чтобы NP = P было открытием, изменившим мир, оно должно привести к полиномиальным решениям низкого порядка. Полиномиально масштабируемое решение бесполезно, если для фактического вычисления все еще требуется возраст Вселенной.

Это отличная история, и я надеюсь, что она настолько повысит осведомленность общественности о компьютерных науках, что станет интересным предметом для изучения.


Добавить комментарий