Tuesday, June 6, 2023

"Есть проблемы гораздо сложнее, чем NP-Complete""Есть проблемы гораздо сложнее, чем NP-Complete", что не вошло в основную публикацию

Travelling Salesman poster
Travelling Salesman (Путешествующий продавец, Коммивояжер) - это интеллектуальный триллер 2012 года о четырех математиках, которые были наняты правительством США для решения самой сложной проблемы в истории информатики - равенства классов сложности P и NP (P versus NP problem).
Чиновник Министерства обороны США предлагает вознаграждение в 10 миллионов долларов за их алгоритм. Только один из четырех выступает против продажи и вынужден раскрыть темную правду, герои фильма «Путешествующий продавец» слишком хорошо осведомлены о том, какие последствия принесёт миру их работа.

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

Скотт Ааронсон (Scott Joel Aaronson), специалист в области теории вычислительных машин и систем, преподаватель факультета компьютерных наук Техасского университета в Остине.


Другая часть статьи: Есть проблемы гораздо сложнее, чем NP-Complete

No comments:

Post a Comment