Попытаюсь всё-таки продвинуться к логическому завершению.
Почему же столь важны оказались именно булевы формулы?
Напомню, булева формула называется выполнимой, если существует такой набор значений входящих в нее переменных, для которого она принимает значение ИСТИНА.
читать дальшеЗадача выполнимости булевых формул (еще она называется SAT (satisfiability) (по-русски: ВЫП — выполнимость)) так и формулируется: можно ли присвоить всем переменным, встречающимся в формуле, значения ЛОЖЬ и ИСТИНА так, чтобы формула стала истинной.
И здесь огромную лепту внес Стивен Кук.
Согласно теореме Кука, доказанной им в 1971-м году, задача SAT NP-полна.
Вообще, в этом знаменательном 1971-м году Стивен Кук написал статью, в которой-то и был впервые введен термин «NP-полная задача», и задача SAT была первой задачей, для которой доказывалось свойство NP-полноты.
В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT.
Впоследствии NP-полнота была доказана и для множества других задач.
Но для доказательства NP-полноты нужны ведь какие-то методы! Как вообще взять задачу, и доказать, что к ней сводится любая другая задача из класса NP? На первый взгляд кажется, что это вещь невыполнимая, по крайней мере, чрезвычайно трудоемкая.
Но на самом деле тут тяжелее всего пришлось Куку! Потому что он доказал NP-полноту впервые! Как раз ему-то и пришлось перебирать все задачи класса NP по одной.
Всем последователям было уже гораздо проще!
Ведь для доказательства NP-полноты некоторой задачи достаточно показать, что к ней за полиномиальное время сводится сама задача SAT! Ха! А если она свелась (а она ведь NP-полна), то, стало быть, наша задача тоже NP-полна! Всё просто! (Хотя, конечно, и в таком виде это ой как непросто!)
Но теперь зато понятно, почему задача SAT стоит особняком.
Вообще же к NP-полным задачам относятся:
Задача о наименьшем числе перестановок в пятнашках
Задача коммивояжёра
Задача раскраски графа
Задача о вершинном покрытии
Задача о покрытии множества
Задача о клике
Жирным я выделила задачи, о которых уже рассказывала.
Ну, кажется, я уже дошла до того, чтобы приступать к проблеме P(?)=NP.
Вообще, эту проблему называют проблемой Кука. И за ее решение положен приз миллион долларов (кажется, я уже об этом писала (?))
Попробую еще раз ее "сформулировать неформально" (простите за оксюморон):
Вернемся к решению задач с подсказками. "Подсказкой" у нас может быть оракул или свидетель. О свидетелях мы уже говорили много. Но приведу еще самый простой пример. Предположим, вы оказались в большом скоплении людей. Скажем, в театре. И вы договорились встретиться "где-то здесь" с другом. Людей много. Вам нужно "оглядеть" каждого, чтобы найти своего друга. Однако же, если кто-то покажет вам пальцем, и скажет: "да вот же он!", — вы узнаете его мгновенно!
Если обобщить такие примеры и сформулировать "общий принцип", мы получим, что решение какой-либо задачи
Стивен Кук сформулировал проблему следующим образом: "может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки?".
Эта проблема является одной из нерешенных проблем логики и информатики.
Ее решение в корне бы изменило основы криптографии (в том случае, если бы равенство классов Р и NP удалось доказать) — вся безопасность информации полетела бы в тартарары. Но об этом в следующий раз.
(При подготовке использовался материал вот отсюда: rc.nsu.ru/text/news/Physics/093.html
Кто хочет получить миллион, посмотрите! Там для вас есть кое-то еще)))