Журнал «Компьютерра» № 6 от 14 февраля 2006 года

Некоторые из задач класса 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-полные. Такова, например, проблема изоморфизма графов: по двум данным графам понять, можно ли перевести вершины одного графа в вершины другого так, чтобы ребра переходили в ребра. Впрочем, подозрения могут и не оправдаться: например, одним из самых громких результатов последних лет был полиномиальный алгоритм для задачи проверки числа на простоту. Примечательно, кстати, что проверка на простоту оказывается принципиально проще, чем разложение на множители[Возможно, это покажется менее странным, если напомнить, что сложность измеряется от длины входа. А длина входа в данном случае — это длина числа в двоичной записи, то есть примерно его логарифм. И алгоритм, чтобы быть полиномиальным от длины входа, должен быть логарифмическим от величины числа, которое нужно проверить на простоту].

Теперь, когда мы поняли формулировку задачи, перейдем к ее обсуждению.