Научная Сеть >> М.Н. Вялый "Сложность вычислительных задач"

Наука >> Математика >> Математическое образование | Популярные статьи

Next: 6. Примеры NP-полных задач Up: Сложность вычислительных задач Previous: 4.2. Класс Contents: Содержание

5. Набросок доказательства теоремы Кука-Левина

1) Это утверждение почти очевидно. Советник сообщает Исполнителю значения переменных, входящих в формулу, при которых она истинна. Исполнитель справится с проверкой истинности полученного высказывания за полиномиальное время.

2) Пусть функция из $\ensuremath{\mathrm {NP}}$ , которую нужно свести к , имеет вид $f(x)= \exists y\:\big((\vert y\vert<q(\vert x\vert))\wedge R(x,y)\big)$ .

Рассмотрим машину Тьюринга, вычисляющую $R(\cdot,\cdot)$ за полиномиальное время. Нам нужно записать в виде логической формулы условие того, что при некотором (и заданном входе ), машина выдает результат 1. Для этого представим весь процесс вычисления, длящегося время $T= \mathop{\mathrm{poly}}\nolimits (n)$ и использующего память $S= \mathop{\mathrm{poly}}\nolimits (n)$ , таблицей вычисления размера $T\times S$ , показанной на рисунке 1.

Рис. 1.

$\begin{figure}{ \begin{displaymath} \begin{array}{l\vert p{7mm}\vert p{7mm}\vert... ...o64mm{\hfill} }}_{S\text{ клеток}}$}} \end{array}\end{displaymath}} \end{figure}$

Строка с номером таблицы задает состояние МТ после тактов работы. Символы $\Gamma_{j,k}$ , записанные в таблице, принадлежат алфавиту ${\cal S}\times\{\emptyset\cup{\cal Q}\}$ . Символ $\Gamma_{j,k}$ определяет пару (символ, записанный в -й ячейке после тактов работы; состояние управляющего устройства после тактов работы, если головка находится над -й ячейкой, в противном случае второй элемент пары - $\emptyset$ ). Для простоты также считаем, что если вычисление заканчивается при некотором входе за тактов, то строки c номерами, большими , повторяют строку с номером .

Состояние каждой клетки таблицы можно закодировать конечным (не зависящим от ) числом булевых переменных. Имеются локальные правила согласования, т. е. состояние каждой клетки $\Gamma$ в строке ниже нулевой однозначно определяется состояниями клеток в предыдущей строке, лежащих непосредственно над данной ( $\Gamma'$ ), левее данной ( $\Gamma'_л$ ) и правее данной ( $\Gamma'_п$ ). Каждое такое условие можно записать в виде логической формулы от переменных, кодирующих состояния клеток, причем размер этой формулы от также не зависит.

Еще нам нужно записать условие успешности вычисления (результат равен 1). Для этого заметим, что без ограничения общности можно считать, что состояния клеток таблицы кодируются так, что одна из кодирующих переменных равна 1 только в том случае, когда в ячейке записана 1. Тогда значение этой переменной для кода $\Gamma_{T,0}$ и будет результатом вычисления.

Определим формулу $\varphi_x$ как конъюнкцию всех формул, в которые подставлены значения переменных, кодирующих вход $x\char93 y$ , дополненный символами $\hbox{\unitlength=1pt\begin{picture}(6,8) \put(0,0){\line(1,0){6}} \put(0,2){\line(1,0){6}} \put(0,0){\line(0,1){2}} \put(6,0){\line(0,1){2}} \end{picture}}$ до длины $\vert x\vert+1+q(\vert x\vert)$ . Значения, соответствующие и $\char93$ , - константы, поэтому переменные, от которых зависит эта формула, отвечают и кодам внутренних ячеек таблицы. Так что можно считать, что формула $\phi_x$ зависит от и еще от каких-то переменных, которые мы обозначим .

Итак, мы сопоставили слову формулу $\varphi_x(y,z)$ , которая по построению обладает следующим свойством. Если выполняется , то найдется такой набор значений , при котором $\varphi_x(y,z(x,y))$ истинна (эти значения описывают работу МТ на входе $x\char93 y$ ). А если не выполняется, то $\varphi_x(y,z)$ всегда ложна (поскольку по сути утверждает, что вычисление на входе дает ответ "да"). Таким образом, при такая формула иногда (при некоторых значениях ) истинна, при - всегда ложна.

Next: 6. Примеры NP-полных задач Up: Сложность вычислительных задач Previous: 4.2. Класс Contents: Содержание

МЦНМО

Написать комментарий