Изменения
Новая страница: «== NP-полнота <tex> \mathrm{BH_{1N}} </tex> == <tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких...»
== NP-полнота <tex> \mathrm{BH_{1N}} </tex> ==
<tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает <tex>1</tex> за время <tex> T(m, x) \le t </tex>.
<tex> \mathrm{BH_{1N}} = \lbrace \langle m, x, 1^t \rangle \bigm| m </tex> {{---}} недетерминированная машина Тьюринга, <tex> m(x) = 1, T(m,x) \le t \rbrace </tex>
{{Теорема
|statement=<tex> \mathrm{BH_{1N}} \in \mathrm{NPC} </tex>
|proof=
# <tex> \mathrm{BH_{1N}} \in \mathrm{NPH} </tex> <br> Нужно доказать, что <tex> \forall \mathrm{L} \in \mathrm{NP} </tex> существует полиномиальное [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведение по Карпу]] к языку <tex> \mathrm{BH_{1N}} </tex>. Рассмотрим произвольный язык <tex> \mathrm{L} \in \mathrm{NP} </tex>. Для него существует машина Тьюринга <tex> m </tex> и полином <tex> p(x) </tex>, такие что <tex> T(m, x) \le p(|x|), \mathrm{L}(m) = \mathrm{L} </tex>. Докажем, что <tex> \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \le_f \mathrm{BH_{1N}} </tex>. Рассмотрим функцию <tex> f(x) = \langle m, x, 1^{p(|x|)} \rangle </tex>, по входным данным возвращающую тройку из описанной выше машины Тьюринга, входных данных и времени <tex> p(|x|)</tex> в унарной системе счисления. <br> <br> Проверим, что <tex> x \in \mathrm{L} \Leftrightarrow f(x) \in \mathrm{BH_{1N}} </tex>. <br> Пусть <tex> x \in L </tex>. Тогда <tex> m(x) = 1 </tex> за время не более <tex> p(|x|) </tex>, а значит <tex>\langle m,x, 1^{p(|x|)} \rangle = f(x) \in \mathrm{BH_{1N}} </tex>. <br> Пусть <tex>x \not\in L</tex>. Тогда <tex>m(x) = 0</tex> и <tex>\langle m,x, 1^{p(|x|)} \rangle = f(x) \notin \mathrm{BH_{1N}} </tex>. <br> <br> Это значит, что <tex> \forall \mathrm{L} \in \mathrm{NP}\ \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \le_f \mathrm{BH_{1N}} </tex>, и из этого следует, что <tex> \mathrm{BH_{1N}} \in \mathrm{NPH} </tex>. <br><br>
# <tex> \mathrm{BH_{1N}} \in \mathrm{NP} </tex> <br>Можно написать недетерминированную программу, которая будет по <tex> \langle m, x, 1^t \rangle </tex> моделировать <tex> t </tex> шагов <tex> m </tex> на входе <tex> x </tex>, выбирая недетерминированно соответствующие недетерминированные переходы, и если машина за это время допустила слово, то только тогда <tex> \langle m, x, 1^t \rangle \in \mathrm{BH_{1N}} </tex>.
}}
== См. также ==
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Недетерминированные вычисления]]
[[Категория: Теория сложности]]
<tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает <tex>1</tex> за время <tex> T(m, x) \le t </tex>.
<tex> \mathrm{BH_{1N}} = \lbrace \langle m, x, 1^t \rangle \bigm| m </tex> {{---}} недетерминированная машина Тьюринга, <tex> m(x) = 1, T(m,x) \le t \rbrace </tex>
{{Теорема
|statement=<tex> \mathrm{BH_{1N}} \in \mathrm{NPC} </tex>
|proof=
# <tex> \mathrm{BH_{1N}} \in \mathrm{NPH} </tex> <br> Нужно доказать, что <tex> \forall \mathrm{L} \in \mathrm{NP} </tex> существует полиномиальное [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведение по Карпу]] к языку <tex> \mathrm{BH_{1N}} </tex>. Рассмотрим произвольный язык <tex> \mathrm{L} \in \mathrm{NP} </tex>. Для него существует машина Тьюринга <tex> m </tex> и полином <tex> p(x) </tex>, такие что <tex> T(m, x) \le p(|x|), \mathrm{L}(m) = \mathrm{L} </tex>. Докажем, что <tex> \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \le_f \mathrm{BH_{1N}} </tex>. Рассмотрим функцию <tex> f(x) = \langle m, x, 1^{p(|x|)} \rangle </tex>, по входным данным возвращающую тройку из описанной выше машины Тьюринга, входных данных и времени <tex> p(|x|)</tex> в унарной системе счисления. <br> <br> Проверим, что <tex> x \in \mathrm{L} \Leftrightarrow f(x) \in \mathrm{BH_{1N}} </tex>. <br> Пусть <tex> x \in L </tex>. Тогда <tex> m(x) = 1 </tex> за время не более <tex> p(|x|) </tex>, а значит <tex>\langle m,x, 1^{p(|x|)} \rangle = f(x) \in \mathrm{BH_{1N}} </tex>. <br> Пусть <tex>x \not\in L</tex>. Тогда <tex>m(x) = 0</tex> и <tex>\langle m,x, 1^{p(|x|)} \rangle = f(x) \notin \mathrm{BH_{1N}} </tex>. <br> <br> Это значит, что <tex> \forall \mathrm{L} \in \mathrm{NP}\ \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \le_f \mathrm{BH_{1N}} </tex>, и из этого следует, что <tex> \mathrm{BH_{1N}} \in \mathrm{NPH} </tex>. <br><br>
# <tex> \mathrm{BH_{1N}} \in \mathrm{NP} </tex> <br>Можно написать недетерминированную программу, которая будет по <tex> \langle m, x, 1^t \rangle </tex> моделировать <tex> t </tex> шагов <tex> m </tex> на входе <tex> x </tex>, выбирая недетерминированно соответствующие недетерминированные переходы, и если машина за это время допустила слово, то только тогда <tex> \langle m, x, 1^t \rangle \in \mathrm{BH_{1N}} </tex>.
}}
== См. также ==
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Недетерминированные вычисления]]
[[Категория: Теория сложности]]
