Журнал «Компьютерра» № 6 от 14 февраля 2006 года - Страница 35
Предельно коротко и нестрого (зато интуитивно) классы P и NP можно описать так: P – это вычислительные задачи, которые легко решить; NP – задачи, для которых легко проверить, верно ли предполагаемое решение. Перейдем к более точным формулировкам.
Начнем с моделей вычислений. Математические модели компьютеров появились раньше, чем сами электронно-вычислительные машины, но задержка оказалась небольшой. В 1936 году Эмиль Пост (Emil Leon Post), а в 1937 году – Алан Тьюринг (Alan Turing) независимо друг от друга разработали теоретическую модель, которая легла в основу теории алгоритмов. Первый программируемый компьютер – механический агрегат под названием Z3 – был создан уже в 1941 году[ЭНИАК – отнюдь не первый компьютер. Сам ЭНИАК был завершен в 1946 году, но в то время программа, по которой он действовал, была «зашита» в железо, и для перепрограммирования ЭНИАКа нужно было менять его схемы]. Идеальный компьютер очень прост (таково общее свойство большинства полезных математических моделей). Он представляет собой бесконечную в одну сторону (пусть справа) ленту, по которой бегает одна-единственная головка. В каждой ячейке ленты может стоять ноль, единица или не стоять ничего. На каждом шаге выполнения алгоритма головка может сдвинуться влево, сдвинуться вправо либо записать в ячейку, над которой она находится, ноль или единицу. Программа для такой машины – это сколь угодно большой, но конечный набор состояний, каждому из которых соответствует некоторое действие, а также следующее состояние. Есть два выделенных состояния – исходное, в котором начинается работа программы, и специальное состояние СТОП, которое соответствует выходу из программы. Например, вот простая программа:
состояние 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-полных задач, на деле сводить одну из них к другой бывает весьма неэффективно. Поэтому лучшие алгоритмы-рекордсмены, да и вообще алгоритмы, предназначенные для практического применения, разрабатываются для каждой задачи отдельно.