Компьютерра - Журнал «Компьютерра» № 6 от 14 февраля 2006 года
состояние 0:
прочесть то, что находится под головкой: если 0, перейти в состояние 1; если 1, перейти в состояние 2; если пусто, перейти в состояние СТОП;
состояние 1:
записать в текущую ячейку 1 и перейти в состояние 3;
состояние 2:
записать в текущую ячейку 0 и перейти в состояние 3;
состояние 3:
сдвинуть головку вправо и перейти в состояние 0.
Она бит за битом инвертирует двоичную строку, записанную на ленте (считаем, что изначально головка находится в крайней левой ячейке, с которой начинается запись числа), а когда строка заканчивается, заканчивает работу и программа.
Эта модель вычислений, получившая название машины Тьюринга, стала общепринятой (хотя Пост придумал свою модель на год раньше). На первый взгляд такой простой объект кажется недостаточным для того, чтобы описать все многообразие компьютерных архитектур, — но пока не известно ни одного алгоритма, который нельзя было бы реализовать на машине Тьюринга. В логике и информатике широко известно нестрогое утверждение (так называемый тезис Черча), которое гласит, что любой объект, отвечающий нашему интуитивному понятию алгоритма, можно реализовать в виде программы на машине Тьюринга. Контрпримеров к этому утверждению пока не обнаружено, и оно считается верным — хотя доказать его, разумеется, невозможно.
Теперь нам нужно научиться оценивать скорость работы различных алгоритмов, сравнивать их друг с другом. Один и тот же алгоритм будет на «Пентиуме» работать несравненно быстрее, чем на машине Тьюринга. Более того, процессор современного компьютера может получить данные из любой ячейки памяти, просто «заказав» соответствующей шине адрес ячейки. А единственной головке машины Тьюринга, чтобы добраться до далеких данных, нужно шаг за шагом пройти всю ленту… Неужели эти изменения не влияют на теоретические оценки времени работы алгоритма?
Разумеется, влияют. Однако во многих принципиальных вопросах теории вычислений, к которым относится и обсуждаемая нами проблема P=?NP, принято считать эквивалентными по сложности такие алгоритмы, время выполнения которых отличается друг от друга полиномиально — то есть на величину, не превосходящую Cn
, где n — объем входной информации («длина входа»), C и d — константы[Отметим, что в теории вычислений невозможно оценивать работу алгоритма иначе, как на бесконечных сериях задач. Для этого используется язык «больших и малых О», пришедший сюда из матанализа. Например, если говорят, что алгоритм выполняется за время O(n•log n) на данном множестве задач, это означает, что существует некоторая константа C, единая для этого множества задач и такая, что алгоритм решает каждую из них не больше, чем за C•n•log n операций, где n — объем начальных данных задачи]. Неформально говоря, в рамках этой теории любые алгоритмы, работающие с «полиномиальной скоростью», считаются быстрыми (хотя на практике время их работы может быть неприемлемо большим). Класс задач, для которых существуют алгоритмы, решающие их за время, полиномиальное от размера входа, и есть тот самый класс P, о котором идет речь в формулировке нашей проблемы.
К классу P принадлежат очень многие известные задачи, — каждый, кто открывал учебники по программированию, помнит, сколько там алгоритмов, работающих за полиномиальное время. В статье «Теория и практика сложности» («КТ» #603) я уже писал о том, что Леонид Хачиян доказал, что в классе P лежит даже кажущаяся неприступно сложной задача линейного программирования.
Однако понять, что такое P, — это еще цветочки. Труднее дать определение класса NP. Формально оно звучит так: это класс задач, которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Можно довольно наглядно охарактеризовать эти задачи, используя понятие машины с подсказкой, хоть это и потребует некоторых усилий.
Рассмотрим для примера задачу выяснения истинности высказывания «заданное число — составное» (то есть у него есть нетривиальные простые делители). Это вычислительно сложная задача (по крайней мере, считается таковой). Однако если нам дали подсказку — предложили кандидата на роль делителя данного числа, — то проверка правильности подсказки очень проста: достаточно по-школьному, в столбик, разделить число на предполагаемый делитель. Эта быстрая операция позволяет сразу заключить: если разделилось без остатка, значит, делитель найден и число действительно составное. В этом случае машина выдает ответ «да». Если же не разделилось — машина, по правилам игры, должна сказать «нет». Ее задача — не найти ответ, а проверить, верно ли, что данная ей подсказка — это правильный ответ. Машина имеет право ошибаться только в одну сторону: она может сказать «нет», если подсказка не подходит (но мы-то понимаем, что может подойти какой-нибудь другой делитель, просто именно этот оказался неправильным), но не имеет права принять неверную подсказку (сказать «да», если делитель-подсказка не делит данное число). Более того, если на самом деле ответ положительный, требуется, чтобы существовала подсказка, которую приняла бы машина (в нашем примере это условие выполнено). Итак, задача входит в класс NP, если существует машина Тьюринга, которая по данной ей подсказке сможет за полиномиальное время либо дать положительный ответ и не ошибиться, либо дать отрицательный ответ с возможной ошибкой; однако для каждого набора данных, ответ на который положителен, должна существовать подсказка, которую примет такая машина Тьюринга.
Некоторые из задач класса NP — так называемые NP-полные задачи — обладают удивительным свойством универсальности: любую задачу из класса NP можно «полиномиально свести» к любой из NP-полных задач[Свести задачу A к задаче B — это значит построить алгоритм, который будет работать за полиномиальное время и решать задачу A, но при этом будет иметь право строить задачи вида B и считать, что они решаются моментально (за один такт). Такого рода вычисления называются вычислениями с оракулом; в данном случае роль оракула выполняет машина, решающая задачу B. Кстати, вычисления с оракулом — отдельная очень интересная тема: если, например, обобщить вопрос P=NP на машины Тьюринга с оракулом, то можно найти такой оракул, для которого P с этим оракулом будет равно NP. Но можно найти и такой оракул, что это равенство будет неверно!]. Вот популярный пример NP-полной задачи: предположим, что в большой компании некоторые люди знакомы друг с другом. Требуется найти размер максимальной группы людей, в которой все будут друг с другом знакомы. Это так называемая задача поиска клики — максимального полного графа. Другой пример — задача коммивояжера: дан набор городов и расстояний между ними, требуется найти кратчайший маршрут, следуя которому можно посетить все города. Третий пример я уже приводил в упомянутой выше статье: это SAT (задача пропозициональной выполнимости), в которой по заданной булевской формуле требуется определить, истинна ли она хоть при каких-нибудь значениях переменных. Эта задача исторически была первой из известных NP-полных задач (ее полноту доказал Стивен Кук (Stephen Cook), и проблему P=?NP иногда в его честь называют проблемой Кука). Несмотря на эквивалентность всех NP-полных задач, на деле сводить одну из них к другой бывает весьма неэффективно. Поэтому лучшие алгоритмы-рекордсмены, да и вообще алгоритмы, предназначенные для практического применения, разрабатываются для каждой задачи отдельно.
Машины, работающие за полиномиальное время с подсказкой, кажутся гораздо мощнее, чем обычные машины без подсказки. Действительно, им нужно всего лишь проверить данный ответ, а обычной машине нужно его сначала найти. Однако вопрос о том, нельзя ли каждую недетерминированную машину Тьюринга превратить в детерминированную, до сих пор открыт. Собственно, это и есть знаменитая проблема равенства классов P и NP.
Учитывая сказанное выше об NP-полных задачах, проблема будет решена положительно, если найдется полиномиальный алгоритм хотя бы для одной NP-полной задачи. Но пока таковых нет даже в перспективе; более того, нет даже субэкспоненциальных алгоритмов (то есть тех, которые бы работали за время, меньшее 2 cn , но большее полиномиального — например, за 2 √ n~). Такие алгоритмы существуют только для задач, которые подозревают в том, что они занимают промежуточное положение — и не полиномиальные, и не NP-полные. Такова, например, проблема изоморфизма графов: по двум данным графам понять, можно ли перевести вершины одного графа в вершины другого так, чтобы ребра переходили в ребра. Впрочем, подозрения могут и не оправдаться: например, одним из самых громких результатов последних лет был полиномиальный алгоритм для задачи проверки числа на простоту. Примечательно, кстати, что проверка на простоту оказывается принципиально проще, чем разложение на множители[Возможно, это покажется менее странным, если напомнить, что сложность измеряется от длины входа. А длина входа в данном случае — это длина числа в двоичной записи, то есть примерно его логарифм. И алгоритм, чтобы быть полиномиальным от длины входа, должен быть логарифмическим от величины числа, которое нужно проверить на простоту].
