Лэнс Фотноу - Золотой билет
Последовательности ДНК содержат закодированную информацию о последовательностях матричных РНК, а те, в свою очередь, хранят информацию о синтезе белков. Белки – или, иначе, протеины – играют ключевую роль в работе клеток, формирующих любой живой организм. Для выполнения своих функций протеин должен особым образом свернуться, т. е. принять определенную пространственную форму. Сложный механизм сворачивания биологами пока не разгадан; известно только, что процессом командуют матричные РНК. Решение проблемы равенства P и NP помогло бы продвинуться на пути понимания этого механизма и, как следствие, – лечения и предотвращения болезней.
В некоторых случаях предсказать пространственную структуру белка помогает статистический метод протягивания, работающий с последовательностями РНК. Впрочем, этот метод тоже требует решения NP-задач, хотя и дает нам лишь самое отдаленное представление о механизмах сворачивания.
Физика
К классу NP принадлежит и проблема поиска состояния минимальной энергии физической системы – например, множества взаимодействующих магнитных частиц или скопления мыльных пузырей. Эффективно находить такие состояния мы пока не умеем. Но разве это не то же самое, что и состояние равновесия? Нет – потому что в состоянии равновесия энергия физической системы не обязательно падает до минимума.
Рис. 3.17. Простейшая физическая система
Рассмотрим простейшую физическую систему: шарик на неровной поверхности (рис. 3.17). При x = 3,0 уровень потенциальной энергии шарика минимален, а при x = 1,0 – нет, хотя шарик будет оставаться в этой точке до тех пор, пока его не толкнут. Таким образом, состояние покоя еще не гарантирует минимального уровня энергии. Поиск состояния минимальной энергии для сложных физических систем – задача чрезвычайно трудная, с которой подчас не справляются не только компьютеры, но и сами физические системы.
С некоторыми особо трудоемкими NP-задачами можно бороться при помощи квантовой механики; подробнее об этом вы узнаете в девятой главе.
Экономика
Менеджер хедж-фонда ищет наилучшую форму помещения капитала. Покупатель в супермаркете старается уложиться в бюджет. Оба сталкиваются с труднейшей вычислительной задачей из класса NP, решить которую получается далеко не всегда, и часто выбирают совсем не оптимальную стратегию. Каким образом отсутствие эффективных с вычислительной точки зрения алгоритмов в различных сферах рынка сказывается на экономике и на жизни общества в целом? Прекрасный вопрос; к сожалению, достойного ответа на него не может дать никто.
В книге «Игры разума» и в одноименном фильме описывается жизнь известного экономиста Джона Нэша. Нэш доказал, что в любом процессе стратегического взаимодействия нескольких сторон, или игроков, существует состояние равновесия, при котором стратегия каждого игрока такова, что он не выиграет от ее изменения в одностороннем порядке. За свою работу ученый спустя несколько десятилетий получил Нобелевскую премию. Доказательство Нэша не дает нам алгоритм поиска оптимальных стратегий; впрочем, позже выяснилось, что эта поисковая задача обладает огромной вычислительной сложностью. Маловероятно, что различные сферы рынка сами, естественным образом, смогут достичь состояния равновесия; по всей видимости, они так и будут непрерывно перетекать из одного состояния в другое, поскольку люди постоянно меняют стратегии в стремлении добиться наилучших результатов.
Математика
В 1928 году выдающийся немецкий математик Давид Гильберт сформулировал свою знаменитую проблему разрешимости – Entscheidungsproblem: существует ли универсальный алгоритм, который для любого математического утверждения определяет, истинно оно или ложно? В 1931 году Курт Гёдель показал, что некоторые утверждения невозможно доказать или опровергнуть ни в одной системе аксиом; спустя несколько лет вдохновленные его результатами Алонзо Чёрч и Алан Тьюринг независимо друг от друга доказали, что универсального алгоритма не существует.
Допустим, у нас есть некое математическое утверждение и нам требуется найти относительно короткое доказательство, которое, к примеру, уместилось бы в тоненькой книжке. Эта задача лежит в классе NP, поскольку оценить длину уже имеющегося доказательства легко, а создать его совсем не просто; будь у нас на руках все возможные доказательства, мы нашли бы искомое обычным перебором. Вот почему математики, которым удалось придумать какое-нибудь хитрое доказательство, становятся знаменитыми.
Определить условия истинности логического выражения тоже иногда бывает очень трудно, даже если выражение это не слишком сложное. Из данной проблемы выросла целая теория, связавшая вместе большинство NP-задач; подробнее мы познакомимся с ней в следующей главе.
Решение головоломки «Путешествие по додекаэдру»
Рис. 3.18. Обход додекаэдра
Глава 4. Самые трудные задачи класса NP
Психолог проводит эксперимент над математиком. Математика посадили в маленький деревянный сарай; на полу лежит лучина для растопки, рядом стоит стол, а на нем – ведро с водой. Психолог поджигает лучину. Математик хватает ведро и заливает огонь водой.
Пока все идет по плану. Психолог повторяет эксперимент, изменив одну незначительную деталь. Математика снова сажают в сарай; внутри тот же стол, на полу такая же лучина, есть и ведро с водой, но стоит оно не на столе, а рядом с лучиной на полу. Психолог поджигает лучину. Математик хватает ведро и ставит его на стол. В результате сарай выгорел дотла; математика, к счастью, успели в последний момент вытащить.
«Почему вы просто не залили огонь?!» – спрашивает психолог. «Я свел новую задачу к уже решенной», – отвечает математик.
Старый математический анекдотПервая NP-полная задача
В 1970 году Том Хал, глава факультета информатики Университета Торонто, загорелся идеей переманить к себе Стивена Кука, которому не хотели давать постоянное место в Калифорнийском университете в Беркли. Зная любовь Кука к парусному спорту, Хал отвез его на озеро Онтарио: он хотел доказать, что в окрестностях Торонто ходить под парусом почти так же приятно, как и в заливе Сан-Франциско. Хитрость удалась, и осенью 1970 года Кук пополнил ряды специалистов Торонтского университета. Со стороны Хала это был блестящий ход, поскольку в скором времени Кук прославился на весь мир и стал самым известным канадским ученым в области теории вычислений.
Кук проводил исследования на стыке математической логики и теоретической информатики. Той осенью он отправил одну из своих работ на рассмотрение комиссии III Международного симпозиума по теории вычислений (Symposium on the Theory of Computing, сокращенно – STOC), проводимого Ассоциацией вычислительной техники. Симпозиум должен был состояться в мае 1971 года. В статье Кука содержались результаты, полученные им задолго до того и не вызвавшие в свое время ажиотажа. Исследования ученого заинтересовали комиссию, и заявку приняли. К началу конференции Кук почти все переделал; в новой статье, которая называлась The Complexity of Theorem-Proving Procedures, он впервые сформулировал проблему равенства классов P и NP и тем самым полностью изменил ход истории.
Чтобы лучше понять результаты Кука, вернемся к рассмотренной в предыдущей главе задаче о клике. Как вы помните, кликой мы называем группу жителей Королевства, в которой все дружат между собой. На представленной ниже схеме дружеских связей Алекс, Кэти и Эрик образуют клику, а вот Алекс, Дэвид и Эрик – нет, поскольку Алекс не дружит с Дэвидом.
Рис. 4.1. Задача о клике
Мы уже знаем, что в Королевстве есть полусекретное и довольно многочисленное сообщество «Альфа». «Альфовцы» утверждают, что все они дружат между собой, т. е. образуют гигантскую клику. Если это действительно так, то какие сведения можно почерпнуть о них из приведенной выше схемы? Теоретически каждый из пяти может входить в «Альфу». Нельзя исключить вероятность того, что Алекс или Дэвид входят в сообщество, однако они не могут быть там одновременно, поскольку дружбы между ними нет; значит, один из них в сообщество точно не входит. Запишем этот вывод в виде логического выражения:
Алекс не в «Альфе» ИЛИ Дэвид не в «Альфе».
«ИЛИ» здесь не исключающее: возможен вариант, при котором ни Алекс, ни Дэвид не входят в сообщество. Алекс и Барбара тоже враждуют, а следовательно – не могут оба входить в «Альфу». Запишем и это:
Алекс не в «Альфе» ИЛИ Барбара не в «Альфе».
