Симпсоны и их математические секреты

Буквально перед исчезновением вселенной Гомера Коэн оставляет для проницательного зрителя особенно интригующий математический фрагмент. В сцене, показанной на приведенном выше рисунке, за левым плечом Гомера в несколько непривычном виде виднеется уравнение Эйлера. Оно также присутствует в эпизоде «ДеньгоБАРТ».

И наконец, в той же сцене за правым плечом Гомера можно увидеть соотношение P = NP. Хотя большинство зрителей даже не заметили бы его, не говоря уже о том, чтобы проанализировать, соотношение P = NP представляет собой ссылку на одну из самых важных нерешенных задач в теории вычислительных систем.

Утверждение P = NP касается двух классов математических задач. P означает polynomial, «полиномиальная задача», а NP – nondeterministic polynomial («недетерминированная полиномиальная задача»). Грубо говоря, задачи класса P легко решить, тогда как задачи класса NP трудно решить, но легко проверить.[51]

* * *

Например, умножение – это легкая задача, которая относится к классу P. Даже если умножаемые числа становятся больше, время на выполнение вычислений увеличивается умеренными темпами.

Напротив, разложение числа на множители (поиск его делителей) – задача класса NP. Она достаточно простая для малых чисел, но для больших становится практически невыполнимой. Например, если вас попросят разложить на множители число 21, вы сразу же найдете ответ: 21 = 3 × 7. Однако разложить на множители число 428 783 гораздо труднее. В действительности вам, возможно, понадобится около часа, чтобы с помощью калькулятора определить: 428 783 = 521 × 823. Важно то, что если бы вам дали числа 521 и 823, вы за несколько секунд смогли бы проверить, являются ли они делителями числа 428 783. Таким образом, разложение на множители – это классическая задача класса NP, поскольку в случае больших чисел ее трудно решить, но легко проверить.

Или… возможно, задача разложения на множители не так сложна, как нам кажется?

В этом случае перед математиками и программистами встает следующий фундаментальный вопрос: действительно ли задачу разложения на множители трудно решить, или мы просто не знаем способа, который бы нам позволил ее упростить? То же касается и множества других задач класса NP: они и правда настолько сложны, или все дело в нашем незнании более доступного варианта их решения?

Этот вопрос представляет собой нечто большее, чем обычный академический интерес, поскольку высокий уровень сложности решения задач класса NP лежит в основе некоторых важных технологий. Например, такие задачи используются в алгоритмах шифрования, опирающихся на предположении о том, что большие числа трудно разложить на множители. Однако если разложение на множители окажется не такой уж сложной задачей и кто-то найдет легкий способ ее решения, это разрушит системы шифрования, что, в свою очередь, поставит под угрозу всеобщую безопасность, от покупок в интернете до международных политических и военных контактов на самом высоком уровне.

Эту проблему часто описывают так: P = NP или P ≠ NP?. Другими словами, могут ли якобы сложные задачи (класса NP) однажды оказаться такими же легкими, как простые задачи (класса P), или нет?

Поиск решения загадки P = NP или P ≠ NP? входит в список самых востребованных математиками задач. Существует даже награда за ее решение. В 2000 году Математический институт Клэя, основанный филантропом Лэндоном Клэем в Кембридже, включил эту задачу в список семи задач тысячелетия, и назначил вознаграждение в 1 миллион долларов за окончательный ответ на вопрос: P = NP или P ≠ NP?.

Дэвид Коэн, который изучал задачи класса P и NP во время учебы в магистратуре Калифорнийского университета в Беркли, подозревает, что в действительности задачи класса NP гораздо проще, чем мы считаем. Именно поэтому соотношение P = NP появляется за плечом Гомера в трехмерной вселенной.

Однако Коэн придерживается мнения меньшинства. Когда в 2002 году специалист по теории вычислительных систем из Университета штата Мэриленд Уильям Газарк провел опрос среди сотни исследователей, только 9 процентов ответили, что P = NP, тогда как 61 процент респондентов отдали предпочтение P ≠ NP. В 2010 году в ходе аналогичного опроса в пользу P ≠ NP высказались уже 81 процент респондентов.

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