Или… возможно, задача разложения на множители не так сложна, как нам кажется?
В этом случае перед математиками и программистами встает следующий фундаментальный вопрос: действительно ли задачу разложения на множители трудно решить, или мы просто не знаем способа, который бы нам позволил ее упростить? То же касается и множества других задач класса 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» можно увидеть такие имена, как Брэд «Колосажатель» Бирд, Оборотень Ли Хартинг, Что-с-тобой-стряслось Грейнинг. А если вы посмотрите очень внимательно, то заметите очаровательную ссылку на теорему Пифагора и автора сценария к фрагменту «Трехмерный Гомер»:
Дэвид² + С.² = Коэн²
ЭКЗАМЕН IV ЭКЗАМЕН НА УРОВНЕ МАГИСТРАТУРЫШутка 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 году Грейнинг в сотрудничестве с Дэвидом Коэном приступил к созданию научно-фантастического мультсериала. Коэн был единомышленником Грейнинга, тоже увлекался научной фантастикой, и особенно полюбил ее после просмотра сериала «Звездный путь». К тому же Коэн очень ценил творчество таких выдающихся писателей-фантастов, как Артур Кларк и Станислав Лем. Именно серьезное отношение к научной фантастике стало для Коэна отправной точкой нового сериала: «Мы с Мэттом Грейнингом с самого начала решили не делать сериал слишком глупым. У нас совсем не было желания высмеивать научную фантастику, разве что сделать ее забавной».
