NP-полнота BH1N — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 7 промежуточных версий 2 участников) | |||
Строка 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> 1^{t} </tex> {{---}} запись <tex> t </tex> в унарной системе счисления. | |
− | То есть <tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, | ||
{{Теорема | {{Теорема | ||
Строка 11: | Строка 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 | + | #:Нужно доказать, что <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 | + | #:Проверим, что <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 | + | #:Это значит, что <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>. |
}} | }} | ||
Строка 21: | Строка 20: | ||
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]] | *[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]] | ||
*[[Недетерминированные вычисления]] | *[[Недетерминированные вычисления]] | ||
+ | |||
[[Категория: Теория сложности]] | [[Категория: Теория сложности]] | ||
+ | [[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ]] | ||
+ | [[Категория: Классы P и NP, NP-полнота]] |
Текущая версия на 19:10, 4 сентября 2022
Определение: |
недетерминированная машина Тьюринга, . | (от bounded halting unary non-deterministic) —
То есть
— язык троек таких, что недетерминированная машина Тьюринга на входной строке возращает за время и — запись в унарной системе счисления.Теорема: |
Доказательство: |
|