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

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

В этом случае перед математиками и программистами встает следующий фундаментальный вопрос: действительно ли задачу разложения на множители трудно решить, или мы просто не знаем способа, который бы нам позволил ее упростить? То же касается и множества других задач класса 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 году «Байки из склепа» прекратили свое существование. Тем не менее у них до сих пор немало поклонников, большинство которых еще даже не родились, когда комикс скоропостижно скончался. К их числу относится и Эл Джин – именно он предложил идею включить видоизмененные титры в эпизоды серии «Маленький домик ужасов на дереве».

Все это объясняет, почему в титрах к эпизоду «Маленький домик ужасов на дереве 6» можно увидеть такие имена, как Брэд «Колосажатель» Бирд, Оборотень Ли Хартинг, Что-с-тобой-стряслось Грейнинг. А если вы посмотрите очень внимательно, то заметите очаровательную ссылку на теорему Пифагора и автора сценария к фрагменту «Трехмерный Гомер»:

Дэвид² + С.² = Коэн²

Шутка 1

Вопрос: Что такое полярный медведь?

Ответ: Прямоугольный медведь после перехода в полярную систему координат.

2 балла

Шутка 2

Вопрос: Что значит «Семь реалов! Семь реалов!»?

Ответ: Попугайская ошибка. (Англ. parroty error («ошибка попугая») созвучно с parity error – «ошибка четности»; испанские монеты выпускались достоинством восемь реалов.)

2 балла

Шутка 3

Рассел Уайтхеду: «Мой Гедель меня убивает!» (Имя Kurt Gödel звучит как kurt girdle, а girdle означает «корсет».)

3 балла

Шутка 4

Вопрос: Что коричневое, пушистое, бежит к морю и эквивалентно аксиоме выбора?

Ответ: Лемминг Цорна (созвучно с «лемма Цорна»).

2 балла

Шутка 5

Вопрос: Что желтое и эквивалентно аксиоме выбора?

Ответ: Лимон Цорна.

2 балла

Шутка 6

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

Ответ: Дело в законе спроса и предложения. (Англ. supply («предложение») созвучно со spline – «сплайн».)

3 балла

Шутка 7

Два математика, Исаак и Готфрид, приходят в паб. Исаак начинает жаловаться на отсутствие математических знаний у простых людей, но Готфрид настроен более оптимистично. Чтобы доказать свою точку зрения, Готфрид ждет, пока Исаак уйдет в туалет, подзывает официантку и объясняет ей, что после возвращения Исаака задаст ей вопрос, на который она должна ответить: «Одна третья икс в кубе». Официантка переспрашивает: «Одна треть яиц вкупе?» Готфрид повторяет свое предложение, на этот раз более медленно: «Одна… третья… икс… в… кубе». Официантка вроде бы понимает (более-менее) и уходит, снова и снова бормоча себе под нос: «Одна треть яиц вкупе».

Вернувшись, Исаак снова выпивает с Готфридом, и спор продолжается. В конце концов Готфрид подзывает официантку, чтобы доказать свою точку зрения: «Исаак, давай проведем эксперимент. Мисс, позвольте мне задать вам простой вопрос по интегральному исчислению. Чему равен интеграл от икс в квадрате?» Официантка останавливается и неуверенно произносит: «Одна треть яиц вкупе». Готфрид самодовольно улыбается, но официантка, уже собираясь уходить, оборачивается, дерзко смотрит на двоих математиков и говорит: «…Плюс константа».

6 баллов

Всего – 20 баллов

Персонажи «Футурамы» (слева направо): Зепп Бранниган (25-звездный генерал и капитан звездолета «Нимбус»); Мамочка (коварная владелица компании MomCorp); профессор Хьюберт Дж. Фарнсворт (160-летний основатель компании Planet Express); Лила (капитан «Межпланетного экспресса»), Бендер (беспутный робот); Филипп Дж. Фрай (парень из ХХ столетия, проснувшийся в XXXI столетии); Зойдберг (врач «Межпланетного экспресса», прибывший с планеты Декапод-10); Киф Крокер (член экипажа «Нимбуса», влюблен в Эми), а также Эми Вонг (член экипажа «Межпланетного экспресса», влюблена в Кифа).

FUTURAMA © 2002 Twentieth Century Fox Television. Все права защищены

Глава 14

Рождение «Футурамы»

После выхода эпизода «Трехмерный Гомер» в октябре 1995 года мультсериал «Симпсоны» поднялся на новый математический уровень, однако Мэтт Грейнинг уже начал подумывать о другом проекте. Его первый анимационный телесериал получил поистине всемирный успех, и телекомпания Fox попросила Грейнинга взяться за родственный сериал.

В 1996 году Грейнинг в сотрудничестве с Дэвидом Коэном приступил к созданию научно-фантастического мультсериала. Коэн был единомышленником Грейнинга, тоже увлекался научной фантастикой, и особенно полюбил ее после просмотра сериала «Звездный путь». К тому же Коэн очень ценил творчество таких выдающихся писателей-фантастов, как Артур Кларк и Станислав Лем. Именно серьезное отношение к научной фантастике стало для Коэна отправной точкой нового сериала: «Мы с Мэттом Грейнингом с самого начала решили не делать сериал слишком глупым. У нас совсем не было желания высмеивать научную фантастику, разве что сделать ее забавной».