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

Например, вскоре после прохождения Гомера через портал вдали от него проносится на первый взгляд случайная последовательность чисел и букв: 46 72 69 6E 6B 20 72 75 6C 65 73 21. На самом деле эти буквы представляют собой числа в шестнадцатеричной системе счисления: в ней используются обычные цифры от 0 до 9, а также еще шесть цифр, обозначенных латинскими буквами от A до F: A = 10, B = 11, C = 12, D = 13, E = 14 и F = 15. Каждая пара шестнадцатеричных цифр представляет символ в коде ASCII (сокр. от American Standard Code for Information Interchange – Американский стандартный код обмена информацией), который является протоколом конвертации букв и знаков препинания в числа, главным образом в компьютерных целях. Согласно протоколу ASCII, число 46 соответствует букве F, 72 – букве r и т. д. Если перевести таким образом всю последовательность, то получится смелое заявление, восхваляющее гиков: Frink rules! («Фринк рулит!»).

Через несколько мгновений в трехмерном пространстве благодаря сценаристу Дэвиду Коэну появляется еще один фрагмент математики:

1782¹² + 1841¹² = 1922¹²

Это еще одно ошибочное доказательство последней теоремы Ферма, наподобие созданного Коэном для эпизода «Волшебник Вечнозеленой аллеи», о котором мы говорили в главе 3. Эти числа тщательно подобраны таким образом, чтобы обе стороны уравнения были почти равны. Если сравнить сумму первых двух степеней с третьей степенью, результат окажется точным до первых девяти цифр, выделенных жирным шрифтом:

1 025 397 835 622 633 634 807 550 462 948 226 174 976 (1 782¹²)

+ 1 515 812 422 991 955 541 481 119 495 194 202 351 681 (1 841¹²)

= 2 541 210 258614 589 176 288 669 958 142 428 526 657

≈ 2 541 210 259314 801 410 819 278 649 643 651 567 616 (1 922¹²)

Это означает, что расхождение между левой и правой частями уравнения составляет всего 0,00000003 процента, но это более чем весомый аргумент, чтобы считать данное решение уравнения ошибочным. На самом деле есть быстрый способ определить, что 1782¹² + 1841¹² = 1922¹² – ложное решение, не прибегая к громоздким вычислениям. Для этого достаточно обратить внимание на присутствие в уравнении четного числа (1782), возведенного в двенадцатую степень, которое в сумме с нечетным числом (1841), также возведенным в двенадцатую степень, предположительно равно четному числу (1922) в двенадцатой степени. Здесь четность и нечетность играют большую роль, поскольку нечетное число, возведенное в любую степень, всегда дает только нечетный результат, тогда как четное число, возведенное в любую степень, дает исключительно четный результат. Исходя из того, что сумма нечетного и четного числа всегда нечетная, левая сторона равенства может быть только нечетной, тогда как правая должна быть четной. Таким образом, очевидно, что это ошибочное решение:

четное¹² + нечетное¹² ≠ четное¹²

Моргните – и пропустите еще пять намеков на нердовские штучки, которые проплывают мимо Гомера в трехмерной вселенной. Первый – вполне безобидный обычный чайник. Почему же он нердовский? Когда в 1975 году один из пионеров компьютерной графики Мартин Ньюэлл из Университета штата Юта решил сгенерировать на компьютере какой-то объект, он выбрал именно этот предмет быта. Чайник был достаточно простым объектом, но в то же время содержал довольно сложные элементы, такие как ручка и кривые поверхности. С тех пор так называемый чайник из Юты стал отраслевым стандартом для демонстрации возможностей компьютерной графики. Именно такой чайник присутствует в сцене с чайной вечеринкой в мультфильме «История игрушек» (Toy Story), в спальне Бу из мультфильма «Корпорация Монстров» (Monsters, Inc.), а также еще в нескольких фильмах.

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

Третий – проносящееся мимо космологическое неравенство ( ρ m 0> 3 H 0² / 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 лежит в основе некоторых важных технологий. Например, такие задачи используются в алгоритмах шифрования, опирающихся на предположении о том, что большие числа трудно разложить на множители. Однако если разложение на множители окажется не такой уж сложной задачей и кто-то найдет легкий способ ее решения, это разрушит системы шифрования, что, в свою очередь, поставит под угрозу всеобщую безопасность, от покупок в интернете до международных политических и военных контактов на самом высоком уровне.