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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
==Определение языка <tex>BH_{1N}</tex>==  
 
==Определение языка <tex>BH_{1N}</tex>==  
Языком <tex>BH_{1N}</tex>(от англ. bounded halting unary) называется множество троек, где <tex>m</tex> - недетерминированная машина Тьюринга (НМТ), <tex>x</tex> - входные данные и <tex>t</tex> - время в унарной системе счисления, таких, что <tex>m(x)=1</tex> и время работы машины <tex>m</tex> на входе <tex>x</tex> <tex>T(m, x)\le t</tex>.
+
Языком <tex>BH_{1N}</tex>(от англ. bounded halting unary) называется множество троек <tex>\langle m, x, 1^{t} \rangle</tex>, где <tex>m</tex> - недетерминированная машина Тьюринга (НМТ), <tex>x</tex> - входные данные и <tex>t</tex> - время в унарной системе счисления, таких, что <tex>m(x)=1</tex> и время работы машины <tex>m</tex> на входе <tex>x</tex> <tex>T(m, x)\le t</tex>.
 
<tex>BH_{1N} = </tex> { <tex>\langle m, x, 1^{t} \rangle | m</tex> - НМТ, <tex>m(x)=1, T(m, x)\le t</tex> }.
 
<tex>BH_{1N} = </tex> { <tex>\langle m, x, 1^{t} \rangle | m</tex> - НМТ, <tex>m(x)=1, T(m, x)\le t</tex> }.
Так же существуют языки <tex>BH_{1D}</tex>, <tex>BH_{2N}</tex>, <tex>BH_{2D}</tex>, отличающиеся от <tex>BH_{1N}</tex> только детерминированностью машин Тьюринга (<tex>D</tex> - детерминированная, <tex>N</tex> - недетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).
+
Так же можно рассматривать языки <tex>BH_{1D}</tex>, <tex>BH_{2N}</tex>, <tex>BH_{2D}</tex>, отличающиеся от <tex>BH_{1N}</tex> только детерминированностью машин Тьюринга (<tex>D</tex> - детерминированная, <tex>N</tex> - недетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).
  
 
==Теорема==  
 
==Теорема==  
 
Язык <tex>BH_{1N}</tex> принадлежит классу <tex>NP</tex>-полных задач: <tex>BH_{1N}\in NPC</tex>.
 
Язык <tex>BH_{1N}</tex> принадлежит классу <tex>NP</tex>-полных задач: <tex>BH_{1N}\in NPC</tex>.
 
==Доказательство==  
 
==Доказательство==  
Для начала докажем, что <tex>BH_{1N}</tex> принадлежит классу <tex>NP</tex>.
+
Для того, чтобы доказать [[Понятие_NP-трудной_и_NP-полной_задачи|NP-полноту]] <tex>BH_{1}</tex> необходимо установить следующие факты:
За время <tex>t</tex> машина Тьюринга может сделать не более <tex>t</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>c*t^{2}</tex>. Проверяющая программа может проэмулировать <tex>m</tex>, затратив полиномиальное количество времени.
+
# <tex> BH_{1} \in NP </tex>.
 +
# <tex> BH_{1} \in NPH </tex>;
 +
 
 +
===Доказательство принадлежности <tex>BH_{1}</tex> классу NP===
 +
Верификатором для <tex>BH_{1}</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>c\point 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>.
 
Если НМТ <tex>m</tex> допускает слово <tex>x</tex> за время <tex>t</tex>, то существует последовательность действий, которые совершает машина <tex>m</tex>, среди которых могут быть и недетерминированные. Следовательно, существует сертификат <tex>y</tex>. Если же слово не допускается или допускается, но за время, большее <tex>t</tex>, то любая последовательность действий не ведет к допуску слова, а значит нет и последовательности недетерминированных выборов, которые могла бы сделать машина <tex>m</tex>.
 
Все условия принадлежности классу <tex>NP</tex> выполнены. Что и требовалось доказать.
 
Все условия принадлежности классу <tex>NP</tex> выполнены. Что и требовалось доказать.
 +
 +
===Доказательство принадлежности <tex>BH_{1}</tex> классу NPH===
 
Теперь докажем, что <tex>BH_{1N}</tex> принадлежит классу <tex>NPH</tex>.
 
Теперь докажем, что <tex>BH_{1N}</tex> принадлежит классу <tex>NPH</tex>.
 
Рассмотрим произвольный язык <tex>L</tex> из класса <tex>NP</tex>. Для него существует машина Тьюринга <tex>m</tex>, такая что <tex>T(m, x)\le p(|x|), L(m) = L</tex>.
 
Рассмотрим произвольный язык <tex>L</tex> из класса <tex>NP</tex>. Для него существует машина Тьюринга <tex>m</tex>, такая что <tex>T(m, x)\le p(|x|), L(m) = L</tex>.

Версия 17:51, 18 марта 2010

Определение языка [math]BH_{1N}[/math]

Языком [math]BH_{1N}[/math](от англ. 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]. [math]BH_{1N} = [/math] { [math]\langle m, x, 1^{t} \rangle | m[/math] - НМТ, [math]m(x)=1, T(m, x)\le t[/math] }. Так же можно рассматривать языки [math]BH_{1D}[/math], [math]BH_{2N}[/math], [math]BH_{2D}[/math], отличающиеся от [math]BH_{1N}[/math] только детерминированностью машин Тьюринга ([math]D[/math] - детерминированная, [math]N[/math] - недетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).

Теорема

Язык [math]BH_{1N}[/math] принадлежит классу [math]NP[/math]-полных задач: [math]BH_{1N}\in NPC[/math].

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

Для того, чтобы доказать NP-полноту [math]BH_{1}[/math] необходимо установить следующие факты:

  1. [math] BH_{1} \in NP [/math].
  2. [math] BH_{1} \in NPH [/math];

Доказательство принадлежности [math]BH_{1}[/math] классу NP

Верификатором для [math]BH_{1}[/math] будет программа [math]R(\langle m, x, 1^{t}\rangle, y)[/math] эмулирующая работу недетерминированной машины Тьюринга [math]m[/math] на слове [math]x[/math]. Там, где у машины [math]m[/math] было несколько выборов, она совершает действие согласно сертификату. При этом проверяется корректность всех действий и замеряется время работы [math]m[/math]. Сертификатом выбираем недетерминированные выборы [math]m[/math]. Длина сертификата по длине меньше, чем [math]c\point 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]. Все условия принадлежности классу [math]NP[/math] выполнены. Что и требовалось доказать.

Доказательство принадлежности [math]BH_{1}[/math] классу NPH

Теперь докажем, что [math]BH_{1N}[/math] принадлежит классу [math]NPH[/math]. Рассмотрим произвольный язык [math]L[/math] из класса [math]NP[/math]. Для него существует машина Тьюринга [math]m[/math], такая что [math]T(m, x)\le p(|x|), L(m) = L[/math]. Докажем, что [math]L[/math] сводится по Карпу к [math] BH_{1N}[/math]. Рассмотрим функцию [math]f(x) = \langle m, x, 1^{p|x|)}\rangle[/math] по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени [math]p(|x|)[/math] в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что [math]x \in L \Leftrightarrow f(x) \in BH_{1N}[/math]. Пусть [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] будет входить в [math]BH_{1N}[/math] согласно его определению. Пусть [math]x \not\in L[/math]. Тогда [math]m(x) = 0[/math]. Но тогда тройка [math]\langle m, x, 1^{t}\rangle[/math] не принадлежит [math]BH_{1N}[/math] при любом [math]t[/math], а значит и при [math]t = p(|x|)[/math]. Значит произвольный язык из класса [math]NP[/math] сводится по Карпу к [math]BH_{1N}[/math], и [math]BH_{1N} \in NPC[/math]. Что и требовалось доказать.