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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 8 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition=<tex> \mathrm{BH_{1N}} = \lbrace \langle m, x, 1^t \rangle \mid m </tex> {{---}} [[Недетерминированные вычисления|недетерминированная машина Тьюринга]], <tex> m(x) = 1, T(m,x) \leqslant t \rbrace </tex>.
+
|definition=<tex> \mathrm{BH_{1N}} </tex> (от ''bounded halting unary non-deterministic'') <tex>= \lbrace \langle m, x, 1^t \rangle \mid m </tex> {{---}} [[Недетерминированные вычисления|недетерминированная машина Тьюринга]], <tex> m(x) = 1, T(m,x) \leqslant t \rbrace </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) \leqslant t </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) \leqslant t </tex> и <tex> 1^{t} </tex> {{---}} запись <tex> t </tex> в унарной системе счисления.
  
 
{{Теорема
 
{{Теорема
Строка 10: Строка 10:
 
#:Можно написать недетерминированную программу, которая будет по <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> \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}} \in \mathrm{NPH} </tex>
 
# <tex> \mathrm{BH_{1N}} \in \mathrm{NPH} </tex>
#:Нужно доказать, что <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) \leqslant p(|x|)</tex> и <tex> \mathrm{L}(m) = \mathrm{L} </tex>. Докажем, что <tex> \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \leqslant_f \mathrm{BH_{1N}} </tex>. Рассмотрим функцию <tex> f(x) = \langle m, x, 1^{p(|x|)} \rangle </tex>, по входным данным возвращающую тройку из описанной выше машины Тьюринга, входных данных и времени <tex> p(|x|)</tex> в унарной системе счисления.
+
#:Нужно доказать, что <tex> \forall L \in \mathrm{NP} </tex> существует полиномиальное [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведение по Карпу]] к языку <tex> \mathrm{BH_{1N}} </tex>. Рассмотрим произвольный язык <tex> L \in \mathrm{NP} </tex>. Для него существует недетерминированная машина Тьюринга <tex> m </tex> и полином <tex> p(x) </tex>, такие что <tex> T(m, x) \leqslant p(|x|)</tex> и <tex> L(m) = L </tex>. Докажем, что <tex> \exists f \in \widetilde{\mathrm{P}} : L \leqslant_f \mathrm{BH_{1N}} </tex>. Рассмотрим функцию <tex> f(x) = \langle m, x, 1^{p(|x|)} \rangle </tex>, по входным данным возвращающую тройку из описанной выше машины Тьюринга, входных данных и времени <tex> p(|x|)</tex> в унарной системе счисления.
#:Проверим, что <tex> x \in \mathrm{L} \Leftrightarrow f(x) \in \mathrm{BH_{1N}} </tex>.
+
#:Проверим, что <tex> x \in L \Leftrightarrow f(x) \in \mathrm{BH_{1N}} </tex>.
 
#:*Пусть <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>.
 
#:*Пусть <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>.
 
#:*Пусть <tex>x \notin L</tex>. Тогда <tex>m(x) = 0</tex> и <tex>\langle m,x, 1^{p(|x|)} \rangle = f(x) \notin \mathrm{BH_{1N}} </tex>.
 
#:*Пусть <tex>x \notin L</tex>. Тогда <tex>m(x) = 0</tex> и <tex>\langle m,x, 1^{p(|x|)} \rangle = f(x) \notin \mathrm{BH_{1N}} </tex>.
#:Это значит, что <tex> \forall \mathrm{L} \in \mathrm{NP}\ \exists f \in \widetilde{\mathrm{P}} : \mathrm{L} \leqslant_f \mathrm{BH_{1N}} </tex>, и из этого следует, что <tex> \mathrm{BH_{1N}} \in \mathrm{NPH} </tex>.
+
#:Это значит, что <tex> \forall L \in \mathrm{NP}\ \exists f \in \widetilde{\mathrm{P}} : L \leqslant_f \mathrm{BH_{1N}} </tex>, и из этого следует, что <tex> \mathrm{BH_{1N}} \in \mathrm{NPH} </tex>.
 
}}
 
}}
  
Строка 20: Строка 20:
 
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 
*[[Недетерминированные вычисления]]
 
*[[Недетерминированные вычисления]]
 +
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]
 +
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ]]
 +
[[Категория: Классы P и NP, NP-полнота]]

Текущая версия на 19:10, 4 сентября 2022

Определение:
[math] \mathrm{BH_{1N}} [/math] (от bounded halting unary non-deterministic) [math]= \lbrace \langle m, x, 1^t \rangle \mid m [/math]недетерминированная машина Тьюринга, [math] m(x) = 1, T(m,x) \leqslant t \rbrace [/math].

То есть [math] \mathrm{BH_{1N}} [/math] — язык троек [math] \langle m, x, 1^t \rangle [/math] таких, что недетерминированная машина Тьюринга [math] m [/math] на входной строке [math] x [/math] возращает [math]1[/math] за время [math] T(m, x) \leqslant t [/math] и [math] 1^{t} [/math] — запись [math] t [/math] в унарной системе счисления.

Теорема:
[math] \mathrm{BH_{1N}} \in \mathrm{NPC} [/math]
Доказательство:
[math]\triangleright[/math]
  1. [math] \mathrm{BH_{1N}} \in \mathrm{NP} [/math]
    Можно написать недетерминированную программу, которая будет по [math] \langle m, x, 1^t \rangle [/math] моделировать [math] t [/math] шагов [math] m [/math] на входе [math] x [/math], выбирая недетерминированно соответствующие недетерминированные переходы, и если машина за это время допустила слово, то только тогда [math] \langle m, x, 1^t \rangle \in \mathrm{BH_{1N}} [/math].
  2. [math] \mathrm{BH_{1N}} \in \mathrm{NPH} [/math]
    Нужно доказать, что [math] \forall L \in \mathrm{NP} [/math] существует полиномиальное сведение по Карпу к языку [math] \mathrm{BH_{1N}} [/math]. Рассмотрим произвольный язык [math] L \in \mathrm{NP} [/math]. Для него существует недетерминированная машина Тьюринга [math] m [/math] и полином [math] p(x) [/math], такие что [math] T(m, x) \leqslant p(|x|)[/math] и [math] L(m) = L [/math]. Докажем, что [math] \exists f \in \widetilde{\mathrm{P}} : L \leqslant_f \mathrm{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 \mathrm{BH_{1N}} [/math].
    • Пусть [math] x \in L [/math]. Тогда [math] m(x) = 1 [/math] за время не более [math] p(|x|) [/math], а значит [math]\langle m,x, 1^{p(|x|)} \rangle = f(x) \in \mathrm{BH_{1N}} [/math].
    • Пусть [math]x \notin L[/math]. Тогда [math]m(x) = 0[/math] и [math]\langle m,x, 1^{p(|x|)} \rangle = f(x) \notin \mathrm{BH_{1N}} [/math].
    Это значит, что [math] \forall L \in \mathrm{NP}\ \exists f \in \widetilde{\mathrm{P}} : L \leqslant_f \mathrm{BH_{1N}} [/math], и из этого следует, что [math] \mathrm{BH_{1N}} \in \mathrm{NPH} [/math].
[math]\triangleleft[/math]

См. также