Изменения
Новая страница: «==Определение языка BH_{1N}== Языком <tex>BH_{1N}</tex>(от англ. bounded halting unary) называется множество трое…»
==Определение языка BH_{1N}==
Языком <tex>BH_{1N}</tex>(от англ. bounded halting unary) называется множество троек, где <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} = {\langle m, x, 1^{t} \rangle | m </tex> - недетерменированная машина Тьюринга, <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 - бинарная).
==Теорема==
Язык <tex>BH_{1N}</tex> принадлежит классу <tex>NP</tex>-полных задач: <tex>BH_{1N}\in NPC</tex>.
==Доказательство==
Для начала докажем, что <tex>BH_{1N}</tex> принадлежит классу <tex>NP</tex>.
За время <tex>t</tex> машина Тьюринга может сделать не более <tex>t</tex> недетерминированных выборов. Сертификатом будет множество этих выборов. Проверяющая сертификаты программа <tex>R(\langle m, x, 1^{t}\rangle, y)</tex> эмулирует работу недетерминированной машины Тьюринга <tex>m</tex> на слове <tex>x</tex>. Там, где у машины <tex>m</tex> было несколько выборов, она совершает действие согласно сертификату. При этом проверяется корректность всех действий и замеряется время работы <tex>m</tex>. Сертификатом выбираем недетерминированные выборы <tex>m</tex>. Длина сертификата по длине меньше, чем <tex>c*t^{2}</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> выполнены. Что и требовалось доказать.
Теперь докажем, что <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>ВH_{1N}</tex>. Рассмотрим функцию <tex>f(x) = \langle m, x, 1^{p|x|)}\rangle</tex> по входным данным возвращающей тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени <tex>p(|x|)</tex> в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что x \in L \Leftrightarrow f(x) \in BH_{1N}.
Пусть <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>T(m, x)\le p(|x|)</tex> значит для какого-то <tex>t: T(m, x)\le t</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>.
Значит произвольный язык из класса <tex>NP</tex> сводится по Карпу к <tex>BH_{1N}</tex>, и <tex>BH_{1N}</tex> принадлежит <tex>NPC</tex>, что и требовалось доказать.
Языком <tex>BH_{1N}</tex>(от англ. bounded halting unary) называется множество троек, где <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} = {\langle m, x, 1^{t} \rangle | m </tex> - недетерменированная машина Тьюринга, <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 - бинарная).
==Теорема==
Язык <tex>BH_{1N}</tex> принадлежит классу <tex>NP</tex>-полных задач: <tex>BH_{1N}\in NPC</tex>.
==Доказательство==
Для начала докажем, что <tex>BH_{1N}</tex> принадлежит классу <tex>NP</tex>.
За время <tex>t</tex> машина Тьюринга может сделать не более <tex>t</tex> недетерминированных выборов. Сертификатом будет множество этих выборов. Проверяющая сертификаты программа <tex>R(\langle m, x, 1^{t}\rangle, y)</tex> эмулирует работу недетерминированной машины Тьюринга <tex>m</tex> на слове <tex>x</tex>. Там, где у машины <tex>m</tex> было несколько выборов, она совершает действие согласно сертификату. При этом проверяется корректность всех действий и замеряется время работы <tex>m</tex>. Сертификатом выбираем недетерминированные выборы <tex>m</tex>. Длина сертификата по длине меньше, чем <tex>c*t^{2}</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> выполнены. Что и требовалось доказать.
Теперь докажем, что <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>ВH_{1N}</tex>. Рассмотрим функцию <tex>f(x) = \langle m, x, 1^{p|x|)}\rangle</tex> по входным данным возвращающей тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени <tex>p(|x|)</tex> в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что x \in L \Leftrightarrow f(x) \in BH_{1N}.
Пусть <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>T(m, x)\le p(|x|)</tex> значит для какого-то <tex>t: T(m, x)\le t</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>.
Значит произвольный язык из класса <tex>NP</tex> сводится по Карпу к <tex>BH_{1N}</tex>, и <tex>BH_{1N}</tex> принадлежит <tex>NPC</tex>, что и требовалось доказать.
