Читать «Журнал «Компьютерра» № 6 от 14 февраля 2006 года» онлайн - страница 93

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

Некоторые из задач класса NP – так называемые NP-полные задачи – обладают удивительным свойством универсальности: любую задачу из класса NP можно «полиномиально свести» к любой из NP-полных задач[Свести задачу A к задаче B – это значит построить алгоритм, который будет работать за полиномиальное время и решать задачу A, но при этом будет иметь право строить задачи вида B и считать, что они решаются моментально (за один такт). Такого рода вычисления называются вычислениями с оракулом; в данном случае роль оракула выполняет машина, решающая задачу B. Кстати, вычисления с оракулом – отдельная очень интересная тема: если, например, обобщить вопрос P=NP на машины Тьюринга с оракулом, то можно найти такой оракул, для которого P с этим оракулом будет равно NP. Но можно найти и такой оракул, что это равенство будет неверно!]. Вот популярный пример NP-полной задачи: предположим, что в большой компании некоторые люди знакомы друг с другом. Требуется найти размер максимальной группы людей, в которой все будут друг с другом знакомы. Это так называемая задача поиска клики – максимального полного графа. Другой пример – задача коммивояжера: дан набор городов и расстояний между ними, требуется найти кратчайший маршрут, следуя которому можно посетить все города. Третий пример я уже приводил в упомянутой выше статье: это SAT (задача пропозициональной выполнимости), в которой по заданной булевской формуле требуется определить, истинна ли она хоть при каких-нибудь значениях переменных. Эта задача исторически была первой из известных NP-полных задач (ее полноту доказал Стивен Кук (Stephen Cook), и проблему P=?NP иногда в его честь называют проблемой Кука). Несмотря на эквивалентность всех NP-полных задач, на деле сводить одну из них к другой бывает весьма неэффективно. Поэтому лучшие алгоритмы-рекордсмены, да и вообще алгоритмы, предназначенные для практического применения, разрабатываются для каждой задачи отдельно.