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

Второй намек – пролетающие мимо Гомера цифры 7, 3 и 4. Это зашифрованная ссылка на компанию Pacific Data Images, которая занималась созданием сцен с компьютерной графикой. Цифры на поле набора телефона ассоциируются с буквами P, D и I, представляющими собой акроним названия компании.

Третий – проносящееся мимо космологическое неравенство (ρm0 > 3H0² / 8πG), описывающее плотность вселенной Гомера. Составленное одним из близких друзей Коэна Дэвидом Шиминовичем, оно подразумевает высокую плотность, а это значит, что сила тяжести в итоге приведет к коллапсу вселенной, что на самом деле и происходит в конце истории.

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

И наконец, в той же сцене за правым плечом Гомера можно увидеть соотношение 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 в фрагмент «Трехмерный Гомер» будет выглядеть несколько неуместным. Однако это не должно стать проблемой в краткосрочной перспективе, поскольку, по мнению половины опрошенных математиков, эта задача не будет решена в текущем столетии.

И наконец, в эпизоде «Трехмерный Гомер» есть еще одна математическая ссылка, заслуживающая упоминания. А если точнее, она появляется в конце всего эпизода «Маленький домик ужасов на дереве 6», в его финальных титрах. По сложившейся традиции титры к эпизодам «Симпсонов», посвященным Хеллоуину, всегда представлены несколько необычно. Например, Мэтт Грейнинг появляется в них как Летучая Мышь Грейнинг, Крыса Грейнинг, Мэтт «Привидение» Грейнинг и Ужасный Мэтт Грейнинг.

Эта традиция возникла под влиянием комиксов под названием «Байки из склепа» (Tales from the Crypt), в которых регулярно появлялись видоизмененные имена авторов и художников. Их издатель, EC Comics, приобрел печальную известность после того, как в 1954 году Подкомитет сената по делам несовершеннолетних провел слушания по вопросу комиксов, по результатам которых был сделан вывод о том, что «Байки из склепа» и другие публикации издательства негативно сказываются на молодом поколении страны. Это привело к тому, что из всех комиксов были удалены зомби, оборотни и им подобные персонажи. В результате в 1955 году «Байки из склепа» прекратили свое существование. Тем не менее у них до сих пор немало поклонников, большинство которых еще даже не родились, когда комикс скоропостижно скончался. К их числу относится и Эл Джин – именно он предложил идею включить видоизмененные титры в эпизоды серии «Маленький домик ужасов на дереве».