Новый ум короля: О компьютерах, мышлении и законах физики

Другая задача, также являющаяся NP- полной [94]— «задача коммивояжера», которая во многом похожа на гамильтонов цикл, если не считать того, что разным сторонам приписаны числа и ставится цель отыскать гамильтонов цикл с минимальной суммой этих чисел (минимальной «длиной» пути, проделанного коммивояжером). Аналогично, «полиномиальное» время решения, достигнутое в «задаче коммивояжера», привело бы к возможности решать все NP- задачи за «полиномиальное» время. (Если такое решение когда-нибудь найдется, то новость об этом сразу попала бы на первые страницы! Ведь к NP- задачам относится, в частности, факторизация больших целых чисел, которая применяется в секретных шифровальных системах, представленных за последние несколько лет. Если эта задача окажется решаемой за «полиномиальное» время, то, возможно, такие шифры могли бы быть взломаны при помощи мощных современных компьютеров; если же нет — эти шифры останутся неприступными. См. Гарднер [1989].)

Эксперты, как правило, полагают, что используя устройство, работающее по принципу машины Тьюринга, невозможно за «полиномиальное» время решить NP- полную задачу; и что, следовательно, Р и NP— неэквивалентны. Это мнение, похоже, верно, хотя пока его никто не смог доказать. И это остается наиболее важной и на сегодняшний день нерешенной задачей теории сложности.

Сложность и вычислимость в физических объектах

Теория сложности является важной для наших рассуждений в этой книге не только потому, что она касается вопроса возможности алгоритмизации, но и потому, что она позволяет для заведомо алгоритмизуемых объектов решать вопрос о том, могут ли использоваться соответствующие алгоритмы на практике. В последующих главах я буду больше говорить о вычислимости, чем о теории сложности, поскольку я склонен думать (хотя, конечно, и не имея для этого достаточных оснований), что, в отличие от фундаментального вопроса вычислимости, положения теории сложности не настолькр значимы для феномена мышления. Более того, мне представляется, что теория сложности сегодня лишь слегка затрагивает вопросы практичности алгоритмов.

Однако, я могу кардинально ошибаться по поводу важности той роли, которую играет сложность. Как будет показано позднее (глава 9, «Квантовые компьютеры»), теория сложности для реальных физических объектов, вероятно, может существенно отличаться от теории, изложенной мной ранее. Чтобы с уверенностью констатировать эту возможную разницу, необходимо будет использовать некоторые волшебные свойства квантовой механики — мистической, но все же поразительно точной теории, описывающей поведение атомов и молекул, а также и другие явления, многие из которых представляют интерес и на макромасштабах. Мы познакомимся с этой теорией в главе 6. Согласно ряду, идей, предложенных Давидом Дойчем [1985], существует принципиальная возможность построить «квантовый компьютер», на котором за «полиномиальное» время могут быть решены некоторые задачи (или классы задач), не принадлежащих Р. Пока совершенно неясно, как на практике сконструировать такое физическое устройство, которое бы (надежно) функционировало по принципу «квантового компьютера» — и, более того, рассматриваемый до сих пор класс задач носил заведомо искусственный характер, — но теоретически понятно, что квантовое физическое устройство могло бы улучшить работу машины Тьюринга.

А есть ли вероятность, что человеческий мозг, который в рамках данного обсуждения я рассматриваю как физическое устройство, хотя и имеющее чрезвычайно тонкую и сложную структуру — может неким образом использовать волшебство квантовой теории? Понимаем ли мы сегодня, как именно квантовые эффекты могут с пользой применяться для решения задач или формирования суждений? Можем ли мы представить, что для использования этих возможных преимуществ нам придется выйти «за нынешние пределы» квантовой теории? Насколько вероятно усовершенствование реальных физических устройств с учетом теории сложности для машин Тьюринга? И что говорит о таких устройствах теория вычислимости?

Чтобы рассматривать эти вопросы, нам надо будет отойти на время от математических абстракций и задаться целью выяснить в следующих главах, как же, в действительности, ведет себя окружающий нас мир!

Глава 5 Классический мир

Состояние физической теории