Алгоритмы и анализ сложности (стр. 9 )

,  .

- число символов алфавита, длина.

3. в любой момент МТ находится в точности в одном состоянии (всего существует различных состояний).

,  .

Длина.

4. в любой момент можно изменить содержимое только одной ячейки (обозреваемой УУ МТ).

,  .

,  длина.

5. очередное МО получается из предыдущего одним переходом, определяемым совокупностью правил перехода.

.

В момент для ячейки , символа и состояния вып-ся:

a) в ячейке не символ ,

b) УУ МТ обозревает не ячейку ,

c) текущее состояние – не ,

d) возможных правил перехода к новому МО, при этом в момент для номеров ячеек вып-ся: .

Число возможных правил длина.

,  длина.

6. в момент 0 выполняются начальные условия:

МТ в состоянии 1, обозревается ячейка 1, первые символов на ленте – входная строка , ячейки содержат 1-й символ алфавита (пустой символ ).

.

Длина.

7. в последний момент МТ находится в заключительном состоянии .

,  длина.

Основные идеи доказательства

1. БФ – это ,  длина БФ (количество использованных переменных) .

В БФ используется всего различных переменных ; если они представлены целыми числами, то для кодирования каждого числа требуется бит.

Таким образом, длина закодированной БФ составляет . Длины БФ и полиномиально связаны, и БФ можно построить за полиномиальное время.

2. По данной допускающей последовательности МО можно так присвоить 0 и 1 переменным , что БФ будет =1.

3. Обратно: если при некотором присвоении 0 и 1 переменным БФ=1, можно найти допускающую последовательность МО.

Из 2 и 3 следует: БФ=1 МТ допускает цепочку .

4. Единственное ограничение на язык , допускаемый МТ – он принадлежит классу

задача выполнимости булевых формул полна.

Связь -полных задач

Теорема 1: задача выполнимости БФ в КНФ полна (следствие теоремы об полноте задачи ВБФ).

1. – уже в КНФ.

2. Преобразуем к КНФ выражения в :

.

3. Длина не зависит от , поэтому перевод в КНФ потребует операций, и увеличит длину в раз.

Теорема 2: задача КНФ-выполнимости полиномиально сводится к задаче 3-КНФ-выполнимости, следовательно,

задача 3-КНФ-выполнимости полна.

Док-во основано на полиномальном сведении КНФ к 3-КНФ.

Пусть , и в КНФ входит скобка .

Введем новые переменные (их значения мы можем задавать произвольно) и преобразуем формулу:

.

Левая и правая части равенства истинны хотя бы одна из переменных . Преобразовав все скобки исходной КНФ получим, что КНФ выполнима 3-КНФ выполнима.

Теорема 3: задача КНФ-выполнимости полиномиально сводится к задаче о -клике, следовательно,

задача о клике полна.

Пусть БФ в КНФ содержит скобок. Граф, для к-го будет решаться задача о -клике, определим следующим образом:

1. Каждому литералу в каждой скобке соот-ет вершина.

2. Ребра соединяют вершины, если вершины соот-ют литералам из разных скобок; при этом если вершины соот-ют одной логической переменной (из разных скобок), то в обоих литералах эти переменные должны использоваться одинаково (либо с отрицанием, либо без).