Редактирование: NP-полнота задачи BH1N

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
==Определение языка BH<sub>1N</sub>==  
+
==Определение языка <tex>BH_{1N}</tex>==  
Языком '''BH<sub>1N</sub>''' (от англ. 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>(от англ. 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> }.
'''BH<sub>1N</sub>''' = <tex>\{ \langle m, x, 1^{t} \rangle | m </tex> &mdash; НМТ, <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 - бинарная).
 
 
Также можно рассматривать языки '''BH<sub>1D</sub>''', '''BH<sub>2N</sub>''', '''BH<sub>2D</sub>''', отличающиеся от '''BH<sub>1N</sub>''' только детерминированностью машин Тьюринга (D - детерминированная, N - недетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).
 
  
 
==Теорема==  
 
==Теорема==  
Язык '''BH<sub>1N</sub>''' является '''NP'''-полным: '''BH<sub>1N</sub>''' ∈ '''NPC'''.
+
Язык <tex>BH_{1N}</tex> принадлежит классу <tex>NP</tex>-полных задач: <tex>BH_{1N}\in NPC</tex>.
 
 
 
==Доказательство==  
 
==Доказательство==  
Для того, чтобы доказать [[Понятие_NP-трудной_и_NP-полной_задачи|'''NP'''-полноту]] '''BH<sub>1N</sub>''' необходимо установить следующие факты:
+
Для того, чтобы доказать [[Понятие_NP-трудной_и_NP-полной_задачи|NP-полноту]] <tex>BH_{1}</tex> необходимо установить следующие факты:
# '''BH<sub>1N</sub>''' ∈ '''NP''';
+
# <tex> BH_{1N} \in NP </tex>.
# '''BH<sub>1N</sub>''' ∈ '''NPH'''.
+
# <tex> BH_{1N} \in NPH </tex>;
 
 
===Доказательство принадлежности BH<sub>1N</sub> классу NP===
 
Будем использовать в качестве сертификата <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>m</tex> допускает слово <tex>x</tex> за время <tex>t</tex>, то существует последовательность действий, которые совершает машина <tex>m</tex>, среди которых могут быть и недетерминированные. Следовательно, существует сертификат <tex>y</tex>. Если же слово не допускается или допускается, но за время, большее <tex>t</tex>, то любая последовательность действий не ведет к допуску слова, а значит нет и последовательности недетерминированных выборов, которые могла бы сделать машина <tex>m</tex>.
 
 
 
Все условия принадлежности классу '''NP''' выполнены.
 
  
===Доказательство принадлежности BH<sub>1N</sub> классу NPH===
+
===Доказательство принадлежности <tex>BH_{1N}</tex> классу NP===
Теперь докажем, что '''BH<sub>1N</sub>''' принадлежит классу '''NPH'''.
+
Верификатором для <tex>BH_{1N}</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>ct</tex>. Значит проверяющая программа может проэмулировать <tex>m</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>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>m</tex> допускает слово <tex>x</tex> за время <tex>t</tex>, то существует последовательность действий, которые совершает машина <tex>m</tex>, среди которых могут быть и недетерминированные. Следовательно, существует сертификат <tex>y</tex>, удовлетворяющий верификатору. Если же слово не допускается или допускается, но за время, большее <tex>t</tex>, то любая последовательность действий не ведет к допуску слова, а значит нет и последовательности недетерминированных выборов, которые могла бы сделать машина <tex>m</tex>.
Пусть <tex>x \not\in L</tex>. Тогда <tex>m(x) = 0</tex>. Но тогда тройка <tex>\langle m, x, 1^{t}\rangle</tex> не принадлежит '''BH<sub>1N</sub>''' при любом <tex>t</tex>, а значит и при <tex>t = p(|x|)</tex>.
+
Все условия принадлежности классу <tex>NP</tex> выполнены.
  
Значит произвольный язык из класса '''NP''' сводится по Карпу к '''BH<sub>1N</sub>''', то есть '''BH<sub>1N</sub>''' ∈ '''NPC'''. Что и требовалось доказать.
+
===Доказательство принадлежности <tex>BH_{1N}</tex> классу NPH===
 +
Теперь докажем, что <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> BH_{1N}</tex>. Рассмотрим функцию <tex>f(x) = \langle m, x, 1^{p|x|)}\rangle</tex> по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени <tex>p(|x|)</tex> в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что <tex>x \in L \Leftrightarrow f(x) \in BH_{1N}</tex>.
 +
Пусть <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> будет входить в <tex>BH_{1N}</tex> согласно его определению.
 +
Пусть <tex>x \not\in L</tex>. Тогда <tex>m(x) = 0</tex>. Но тогда тройка <tex>\langle m, x, 1^{t}\rangle</tex> не принадлежит <tex>BH_{1N}</tex> при любом <tex>t</tex>, а значит и при <tex>t = p(|x|)</tex>.
  
[[Категория:NP]]
+
Значит произвольный язык из класса <tex>NP</tex> сводится по Карпу к <tex>BH_{1N}</tex>, и <tex>BH_{1N} \in NPC</tex>. Что и требовалось доказать.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)