NP-полнота задачи BH1N — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение языка BH1N)
(не показаны 3 промежуточные версии 1 участника)
Строка 15: Строка 15:
  
 
===Доказательство принадлежности BH<sub>1N</sub> классу NP===
 
===Доказательство принадлежности BH<sub>1N</sub> классу NP===
Будем использовать в качестве сертификата <tex>y</tex> последовательность недетерминированных выборов, которые должна сделать машина <tex>m</tex>, чтобы допустить слово <tex>x</tex>. Длина сертификата меньше, чем <tex>ct</tex>.  
+
Будем использовать в качестве сертификата <tex>y</tex> последовательность недетерминированных выборов, которые должна сделать машина <tex>m</tex>, чтобы допустить слово <tex>x</tex>. Длина сертификата меньше, чем <tex>Ct</tex> для некоторого <tex>C</tex>.  
  
 
Для проверки сертификата используется программа <tex>R(\langle m, x, 1^{t}\rangle, y)</tex>, эмулирующая работу недетерминированной машины Тьюринга <tex>m</tex> на слове <tex>x</tex>. Там, где у машины <tex>m</tex> было несколько выборов, <tex>R</tex> совершает действие согласно сертификату. При этом замеряется время работы машины <tex>t</tex>. Проверяющая программа может проэмулировать <tex>m</tex>, затратив полиномиальное количество времени.
 
Для проверки сертификата используется программа <tex>R(\langle m, x, 1^{t}\rangle, y)</tex>, эмулирующая работу недетерминированной машины Тьюринга <tex>m</tex> на слове <tex>x</tex>. Там, где у машины <tex>m</tex> было несколько выборов, <tex>R</tex> совершает действие согласно сертификату. При этом замеряется время работы машины <tex>t</tex>. Проверяющая программа может проэмулировать <tex>m</tex>, затратив полиномиальное количество времени.
Строка 26: Строка 26:
 
Теперь докажем, что '''BH<sub>1N</sub>''' принадлежит классу '''NPH'''.
 
Теперь докажем, что '''BH<sub>1N</sub>''' принадлежит классу '''NPH'''.
 
Рассмотрим произвольный язык <tex>L</tex> из класса '''NP'''. Для него существует машина Тьюринга <tex>m</tex>, такая что <tex>T(m, x)\le p(|x|), L(m) = L</tex>.
 
Рассмотрим произвольный язык <tex>L</tex> из класса '''NP'''. Для него существует машина Тьюринга <tex>m</tex>, такая что <tex>T(m, x)\le p(|x|), L(m) = L</tex>.
Докажем, что <tex>L</tex> сводится по Карпу к '''BH<sub>1N</sub>'''. Рассмотрим функцию <tex>f(x) = \langle m, x, 1^{p|x|)}\rangle</tex> по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени <tex>p(|x|)</tex> в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что <tex>x \in L \Leftrightarrow f(x)</tex> ∈ '''BH<sub>1N</sub>'''.
+
Докажем, что <tex>L</tex> сводится по Карпу к '''BH<sub>1N</sub>'''. Рассмотрим функцию <tex>f(x) = \langle m, x, 1^{p(|x|)}\rangle</tex> по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени <tex>p(|x|)</tex> в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что <tex>x \in L \Leftrightarrow f(x)</tex> ∈ '''BH<sub>1N</sub>'''.
  
 
Пусть <tex>x \in L</tex>. Тогда <tex>m(x) = 1</tex>. Время работы <tex>m</tex> не больше <tex>p(|x|)</tex>, а значит слово <tex>x</tex> будет допущено машиной <tex>m</tex> за время не больше, чем <tex>p(|x|)</tex>. А тогда тройка <tex>\langle m,x, 1^{p(|x|)}\rangle = f(x)</tex> будет входить в '''BH<sub>1N</sub>''' согласно его определению.
 
Пусть <tex>x \in L</tex>. Тогда <tex>m(x) = 1</tex>. Время работы <tex>m</tex> не больше <tex>p(|x|)</tex>, а значит слово <tex>x</tex> будет допущено машиной <tex>m</tex> за время не больше, чем <tex>p(|x|)</tex>. А тогда тройка <tex>\langle m,x, 1^{p(|x|)}\rangle = f(x)</tex> будет входить в '''BH<sub>1N</sub>''' согласно его определению.
Строка 32: Строка 32:
  
 
Значит произвольный язык из класса '''NP''' сводится по Карпу к '''BH<sub>1N</sub>''', то есть '''BH<sub>1N</sub>''' ∈ '''NPC'''. Что и требовалось доказать.
 
Значит произвольный язык из класса '''NP''' сводится по Карпу к '''BH<sub>1N</sub>''', то есть '''BH<sub>1N</sub>''' ∈ '''NPC'''. Что и требовалось доказать.
 +
 +
[[Категория:NP]]

Версия 00:54, 11 октября 2019

Определение языка BH1N

Языком BH1N (от англ. bounded halting unary) называется множество троек [math]\langle m, x, 1^{t} \rangle[/math], где [math]m[/math] - недетерминированная машина Тьюринга (НМТ), [math]x[/math] - входные данные и [math]t[/math] - время в унарной системе счисления, таких, что [math]m(x)=1[/math] и время работы машины [math]m[/math] на входе [math]x[/math] [math]T(m, x)\le t[/math]:

BH1N = [math]\{ \langle m, x, 1^{t} \rangle | m [/math] — НМТ, [math] m(x)=1, T(m, x)\le t \}[/math].

Также можно рассматривать языки BH1D, BH2N, BH2D, отличающиеся от BH1N только детерминированностью машин Тьюринга (D - детерминированная, N - недетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).

Теорема

Язык BH1N является NP-полным: BH1NNPC.

Доказательство

Для того, чтобы доказать NP-полноту BH1N необходимо установить следующие факты:

  1. BH1NNP;
  2. BH1NNPH.

Доказательство принадлежности BH1N классу NP

Будем использовать в качестве сертификата [math]y[/math] последовательность недетерминированных выборов, которые должна сделать машина [math]m[/math], чтобы допустить слово [math]x[/math]. Длина сертификата меньше, чем [math]Ct[/math] для некоторого [math]C[/math].

Для проверки сертификата используется программа [math]R(\langle m, x, 1^{t}\rangle, y)[/math], эмулирующая работу недетерминированной машины Тьюринга [math]m[/math] на слове [math]x[/math]. Там, где у машины [math]m[/math] было несколько выборов, [math]R[/math] совершает действие согласно сертификату. При этом замеряется время работы машины [math]t[/math]. Проверяющая программа может проэмулировать [math]m[/math], затратив полиномиальное количество времени.

Если НМТ [math]m[/math] допускает слово [math]x[/math] за время [math]t[/math], то существует последовательность действий, которые совершает машина [math]m[/math], среди которых могут быть и недетерминированные. Следовательно, существует сертификат [math]y[/math]. Если же слово не допускается или допускается, но за время, большее [math]t[/math], то любая последовательность действий не ведет к допуску слова, а значит нет и последовательности недетерминированных выборов, которые могла бы сделать машина [math]m[/math].

Все условия принадлежности классу NP выполнены.

Доказательство принадлежности BH1N классу NPH

Теперь докажем, что BH1N принадлежит классу NPH. Рассмотрим произвольный язык [math]L[/math] из класса NP. Для него существует машина Тьюринга [math]m[/math], такая что [math]T(m, x)\le p(|x|), L(m) = L[/math]. Докажем, что [math]L[/math] сводится по Карпу к BH1N. Рассмотрим функцию [math]f(x) = \langle m, x, 1^{p(|x|)}\rangle[/math] по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени [math]p(|x|)[/math] в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что [math]x \in L \Leftrightarrow f(x)[/math]BH1N.

Пусть [math]x \in L[/math]. Тогда [math]m(x) = 1[/math]. Время работы [math]m[/math] не больше [math]p(|x|)[/math], а значит слово [math]x[/math] будет допущено машиной [math]m[/math] за время не больше, чем [math]p(|x|)[/math]. А тогда тройка [math]\langle m,x, 1^{p(|x|)}\rangle = f(x)[/math] будет входить в BH1N согласно его определению. Пусть [math]x \not\in L[/math]. Тогда [math]m(x) = 0[/math]. Но тогда тройка [math]\langle m, x, 1^{t}\rangle[/math] не принадлежит BH1N при любом [math]t[/math], а значит и при [math]t = p(|x|)[/math].

Значит произвольный язык из класса NP сводится по Карпу к BH1N, то есть BH1NNPC. Что и требовалось доказать.