Swetlana писал(а):Source of the post Предлагаю модераторам компутер сайенс сделать тему с названием
"Что вы всегда хотели узнать о
сексе о NP-полноте, но боялись спросить", не всё же об антивирусниках писать
Вообще, какбе
секс NP-полнота - это матан в чистом виде, а не CS.
Сам Гэри-Джонсон неужели устарел?! Не, там же теоремы...
Ну это уже юмор Для проверки числа на простоту найден полиномиальный алгоритм, но его еще никто не запрограммировал.
Попробую и я кратко (но я не лектор, получится сумбурно). Предполагаю, что всем понятно, что такое машина Тьюринга (далее МТ).
Рассматриваются массовые задачи и алгоритмы их решения. Массовая задача - это множество однородных задач, параметризованных каким-то параметром
![$$n$$ $$n$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24n%24%24)
. Алгоритм ее решения - МТ, у которой в начальном состоянии на ленте записаны входные данные любого экземпляра массовой задачи. МТ читает их и выдает ответ за некоторое число шагов
![$$t_n$$ $$t_n$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24t_n%24%24)
. Если существует многочлен
![$$P(n): t_n\leqslant P(n)$$ $$P(n): t_n\leqslant P(n)$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24P%28n%29%3A%20t_n%5Cleqslant%20P%28n%29%24%24)
(т.е. если время решения задачи полиномиально - ограничено сверху многочленом от
![$$n$$ $$n$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24n%24%24)
), то говорят, что задача принадлежит классу
![$$P$$ $$P$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24P%24%24)
. Далее вводятся в рассмотрение недетерминированные машины Тьюринга НДМТ. НДМТ - это МТ с некоторым устройством (оракул?), устройство сначала пишет, не читая входные данные, на ленте ответ, а МТ его проверяет за полиномиальное время. Если задача может быть решена НДМТ, то говорят, что она принадлежит классу
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
. Грубо говоря,
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-задачи, это те, у которых ответ проверяется за полиномиальное время.
Ясно, что
![$$P\subset NP$$ $$P\subset NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24P%5Csubset%20NP%24%24)
, поскольку МТ, решающая задачу за полиномиальное время, выпишет и ее ответ не дольше чем за полиномиальное время.
Далее, используется идея универсальности: все
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-задачи сводят к одной задаче ВЫПОЛНИМОСТЬ (или 3-ВЫПОЛНИМОСТЬ - не помню) (по-аглицки - SAT или
![$$k-SAT$$ $$k-SAT$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24k-SAT%24%24)
, именно ее и пытался решить индийский математик). Задача ВЫПОЛНИМОСТЬ следующая: дана конъюнктивная нормальная форма КНФ от
![$$n$$ $$n$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24n%24%24)
переменных длинной не более чем полином от
![$$n$$ $$n$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24n%24%24)
, нужно определить ее решение (пример:
![$$(x_1\vee x_2\vee x_4)\wedge (x_2\veex_3\vee\neg x_4)\wedge \neg x_1=1$$ $$(x_1\vee x_2\vee x_4)\wedge (x_2\veex_3\vee\neg x_4)\wedge \neg x_1=1$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%28x_1%5Cvee%20x_2%5Cvee%20x_4%29%5Cwedge%20%28x_2%5Cveex_3%5Cvee%5Cneg%20x_4%29%5Cwedge%20%5Cneg%20x_1%3D1%24%24)
). Ясно, что задача ВЫПОЛНИМОСТЬ является
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-задачей: оракул пишет решение за
![$$O(n)$$ $$O(n)$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24O%28n%29%24%24)
шагов, а проверка происходит за
![$$O(L(n))$$ $$O(L(n))$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24O%28L%28n%29%29%24%24)
шагов, где
![$$L$$ $$L$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24L%24%24)
- длина КНФ. Сведение всех
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-задач к задаче ВЫПОЛНИМОСТЬ - это теорема Кука на 5 страниц, но суть ее очень проста: действие МТ (следует вспомнить, что МТ - это лента длиной не более многочлена от
![$$n$$ $$n$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24n%24%24)
, конечный алфавит
![$$A$$ $$A$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24A%24%24)
, конечное число состояний
![$$Q$$ $$Q$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24Q%24%24)
и конечное число правил преобразований вида
![$$a_iq_j\to a_kq_m T$$ $$a_iq_j\to a_kq_m T$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24a_iq_j%5Cto%20a_kq_m%20T%24%24)
) кодируется множеством высказываний, конъюнкция которых и составит КНФ (довольно длинную, но полиномиальной длины). В доказательстве приводится явное кодирование всех деталей работы МТ, мы ограничимся примерами (пишу по памяти, могу наврать):
![$$t$$ $$t$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24t%24%24)
- момент времени работы НДМТ (
![$$t=0,1,...,Q(n)$$ $$t=0,1,...,Q(n)$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24t%3D0%2C1%2C...%2CQ%28n%29%24%24)
),
![$$X_{t,k,a}=1\Leftrightarrow$$ $$X_{t,k,a}=1\Leftrightarrow$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24X_%7Bt%2Ck%2Ca%7D%3D1%5CLeftrightarrow%24%24)
в ячейке ленты с номером
![$$k$$ $$k$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24k%24%24)
(поскольку задача -
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
, то длина ленты не более полиномиальной длины) в момент времени
![$$t$$ $$t$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24t%24%24)
находится символ
![$$a$$ $$a$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24a%24%24)
. Число переменных
![$$X_{t,k,a}$$ $$X_{t,k,a}$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24X_%7Bt%2Ck%2Ca%7D%24%24)
не превосходит полинома от
![$$n$$ $$n$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24n%24%24)
, потому мы можем закодировать состояние ленты во все моменты времени работы НДМТ. Далее также кодируются состояния МТ (булевы переменные типа "в момент
![$$t$$ $$t$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24t%24%24)
НДМТ находится в состоянии
![$$q$$ $$q$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24q%24%24)
"), правила работы НДМТ в виде импликаций, которые переписываются в виде множества дизъюнкций, входные данные (уже закодировали) и итоговый ответ тоже. В итоге, мы любую
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-задачу конструктивным образом свели к задаче ВЫПОЛНИМОСТЬ.
Задача, к которой м.б. сведена любая задача называется
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-полной задачей. Теорема Кука нам показывает, что
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-полная задача существует - это задача ВЫПОЛНИМОСТЬ. Далее, товарищи ученые собирают чисто эмпирически множество разных задач и показывают, что они относятся к классу
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
. Простой эквивалентностью устанавливается подкласс
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-задач - это
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-полные задачи - это класс эквивалентности задач, эквивалентных задаче ВЫПОЛНИМОСТЬ.
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-полных задач чуть менее чем дофига и они очень просты: решение системы булевых линейных ограничений, поиск клики, максимального независимого множества на графе, поиск вершинных и реберных покрытий, поиск паросочетаний, задача коммивояжера и т.п. Эквивалентность доказывается явным способом. Например, задача ВЫПОЛНИМОСТЬ может быть сведена к задаче булева линейного программирования (ЦЛП) так: множеству переменных
![$$x_j$$ $$x_j$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24x_j%24%24)
одной задачи биективно ставится в соответствие множество переменных задачи БЛП
![$$y_j$$ $$y_j$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24y_j%24%24)
(
![$$x_j\leftrightarrow y_j$$ $$x_j\leftrightarrow y_j$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24x_j%5Cleftrightarrow%20y_j%24%24)
), большой конъюнкции ставится в соответствие система, а элементарным дизъюнкциям
![$$x_{a_1}\vee...\vee x_{a_k}\leftrightarrow y_{a_1}+...+y_{a_k}\geqslant 1$$ $$x_{a_1}\vee...\vee x_{a_k}\leftrightarrow y_{a_1}+...+y_{a_k}\geqslant 1$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24x_%7Ba_1%7D%5Cvee...%5Cvee%20x_%7Ba_k%7D%5Cleftrightarrow%20y_%7Ba_1%7D%2B...%2By_%7Ba_k%7D%5Cgeqslant%201%24%24)
. Получается, что мы одну и ту же по сложности задачу можем преобразовывать в очень разные задачи. Например, БЛП от ВЫПОЛНИМОСТИ отличается сильно: ЦЛП можно сводить к задачам ЛП и решать методом Гомори - изоморфный алгоритм для задачи ВЫПОЛНИМОСТЬ, мягко говоря, неочевиден. По мере сведения
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-полных задач друг к другу товарищи ученые есс-но пытались решить хотя бы одну из них. Но эквивалентность держиться: ни для одной
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-полной задачи полиномиальный алгоритм решения не придуман. Данный факт какбе намекает нам, что это неспроста. Отсюда и появилась гипотеза
![$$P?=NP$$ $$P?=NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24P%3F%3DNP%24%24)
(которая, ИМХО, решается отрицательно, либо неразрешима вообще).
Заметим также, что есть еще логическая формулировка проблемы, я ее не знаю. Есть также множество задач (например, факторизация и, кажется, изоморфизм графов), которые неизвестно -
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-полные они или все-таки относятся к
![$$P$$ $$P$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24P%24%24)
. Есть множество
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-задач, для которых
![$$NP$$ $$NP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24NP%24%24)
-полнота не доказана. Есть еще какой-то класс
![$$coNP$$ $$coNP$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24coNP%24%24)
и
![$$SPACE$$ $$SPACE$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24SPACE%24%24)
, но я про них не знаю ничего.
Читайте книжки, короче.