NP-полнота задачи BH1N
Содержание
Определение языка BH1N[править]
Языком BH1N (от англ. bounded halting unary) называется множество троек
, где - недетерминированная машина Тьюринга (НМТ), - входные данные и - время в унарной системе счисления, таких, что и время работы машины на входе :BH1N =
— НМТ, .Также можно рассматривать языки BH1D, BH2N, BH2D, отличающиеся от BH1N только детерминированностью машин Тьюринга (D - детерминированная, N - недетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).
Теорема[править]
Язык BH1N является NP-полным: BH1N ∈ NPC.
Доказательство[править]
Для того, чтобы доказать NP-полноту BH1N необходимо установить следующие факты:
- BH1N ∈ NP;
- BH1N ∈ NPH.
Доказательство принадлежности BH1N классу NP[править]
Будем использовать в качестве сертификата
последовательность недетерминированных выборов, которые должна сделать машина , чтобы допустить слово . Длина сертификата меньше, чем для некоторого .Для проверки сертификата используется программа
, эмулирующая работу недетерминированной машины Тьюринга на слове . Там, где у машины было несколько выборов, совершает действие согласно сертификату. При этом замеряется время работы машины . Проверяющая программа может проэмулировать , затратив полиномиальное количество времени.Если НМТ
допускает слово за время , то существует последовательность действий, которые совершает машина , среди которых могут быть и недетерминированные. Следовательно, существует сертификат . Если же слово не допускается или допускается, но за время, большее , то любая последовательность действий не ведет к допуску слова, а значит нет и последовательности недетерминированных выборов, которые могла бы сделать машина .Все условия принадлежности классу NP выполнены.
Доказательство принадлежности BH1N классу NPH[править]
Теперь докажем, что BH1N принадлежит классу NPH. Рассмотрим произвольный язык
из класса NP. Для него существует машина Тьюринга , такая что . Докажем, что сводится по Карпу к BH1N. Рассмотрим функцию по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что ∈ BH1N.Пусть
. Тогда . Время работы не больше , а значит слово будет допущено машиной за время не больше, чем . А тогда тройка будет входить в BH1N согласно его определению. Пусть . Тогда . Но тогда тройка не принадлежит BH1N при любом , а значит и при .Значит произвольный язык из класса NP сводится по Карпу к BH1N, то есть BH1N ∈ NPC. Что и требовалось доказать.