Изменения

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

NP-полнота задачи BH1N

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

Навигация