NP-полнота задачи BH1N — различия между версиями
(→Доказательство принадлежности BH_{1} классу NP) |
(→Доказательство принадлежности BH_{1} классу NP) |
||
Строка 11: | Строка 11: | ||
# <tex> BH_{1} \in NPH </tex>; | # <tex> BH_{1} \in NPH </tex>; | ||
− | ===Доказательство принадлежности <tex>BH_{ | + | ===Доказательство принадлежности <tex>BH_{1N}</tex> классу NP=== |
− | Верификатором для <tex>BH_{ | + | Верификатором для <tex>BH_{1N}</tex> будет программа <tex>R(\langle m, x, 1^{t}\rangle, y)</tex>, эмулирующая работу недетерминированной машины Тьюринга <tex>m</tex> на слове <tex>x</tex>. Там, где у машины <tex>m</tex> было несколько выборов, она совершает действие согласно сертификату. При этом проверяется корректность всех действий и замеряется время работы <tex>m</tex>. Сертификатом выбираем недетерминированные выборы <tex>m</tex>. Длина сертификата меньше, чем <tex>ct</tex>. Значит проверяющая программа может проэмулировать <tex>m</tex>, затратив полиномиальное количество времени. |
Если НМТ <tex>m</tex> допускает слово <tex>x</tex> за время <tex>t</tex>, то существует последовательность действий, которые совершает машина <tex>m</tex>, среди которых могут быть и недетерминированные. Следовательно, существует сертификат <tex>y</tex>. Если же слово не допускается или допускается, но за время, большее <tex>t</tex>, то любая последовательность действий не ведет к допуску слова, а значит нет и последовательности недетерминированных выборов, которые могла бы сделать машина <tex>m</tex>. | Если НМТ <tex>m</tex> допускает слово <tex>x</tex> за время <tex>t</tex>, то существует последовательность действий, которые совершает машина <tex>m</tex>, среди которых могут быть и недетерминированные. Следовательно, существует сертификат <tex>y</tex>. Если же слово не допускается или допускается, но за время, большее <tex>t</tex>, то любая последовательность действий не ведет к допуску слова, а значит нет и последовательности недетерминированных выборов, которые могла бы сделать машина <tex>m</tex>. |
Версия 17:57, 18 марта 2010
Содержание
Определение языка
Языком
(от англ. bounded halting unary) называется множество троек , где - недетерминированная машина Тьюринга (НМТ), - входные данные и - время в унарной системе счисления, таких, что и время работы машины на входе . { - НМТ, }. Так же можно рассматривать языки , , , отличающиеся от только детерминированностью машин Тьюринга ( - детерминированная, - недетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).Теорема
Язык
принадлежит классу -полных задач: .Доказательство
Для того, чтобы доказать NP-полноту необходимо установить следующие факты:
- .
- ;
Доказательство принадлежности классу NP
Верификатором для
будет программа , эмулирующая работу недетерминированной машины Тьюринга на слове . Там, где у машины было несколько выборов, она совершает действие согласно сертификату. При этом проверяется корректность всех действий и замеряется время работы . Сертификатом выбираем недетерминированные выборы . Длина сертификата меньше, чем . Значит проверяющая программа может проэмулировать , затратив полиномиальное количество времени.Если НМТ
допускает слово за время , то существует последовательность действий, которые совершает машина , среди которых могут быть и недетерминированные. Следовательно, существует сертификат . Если же слово не допускается или допускается, но за время, большее , то любая последовательность действий не ведет к допуску слова, а значит нет и последовательности недетерминированных выборов, которые могла бы сделать машина . Все условия принадлежности классу выполнены. Что и требовалось доказать.Доказательство принадлежности классу NPH
Теперь докажем, что
принадлежит классу . Рассмотрим произвольный язык из класса . Для него существует машина Тьюринга , такая что . Докажем, что сводится по Карпу к . Рассмотрим функцию по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что . Пусть . Тогда . Время работы не больше , а значит слово будет допущено машиной за время не больше, чем . А тогда тройка будет входить в согласно его определению. Пусть . Тогда . Но тогда тройка не принадлежит при любом , а значит и при . Значит произвольный язык из класса сводится по Карпу к , и . Что и требовалось доказать.