Редактирование: NP-полнота задачи BH1N

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 26: Строка 26:
 
Теперь докажем, что '''BH<sub>1N</sub>''' принадлежит классу '''NPH'''.
 
Теперь докажем, что '''BH<sub>1N</sub>''' принадлежит классу '''NPH'''.
 
Рассмотрим произвольный язык <tex>L</tex> из класса '''NP'''. Для него существует машина Тьюринга <tex>m</tex>, такая что <tex>T(m, x)\le p(|x|), L(m) = L</tex>.
 
Рассмотрим произвольный язык <tex>L</tex> из класса '''NP'''. Для него существует машина Тьюринга <tex>m</tex>, такая что <tex>T(m, x)\le p(|x|), L(m) = L</tex>.
Докажем, что <tex>L</tex> сводится по Карпу к '''BH<sub>1N</sub>'''. Рассмотрим функцию <tex>f(x) = \langle m, x, 1^{p(|x|)}\rangle</tex> по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени <tex>p(|x|)</tex> в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что <tex>x \in L \Leftrightarrow f(x)</tex> ∈ '''BH<sub>1N</sub>'''.
+
Докажем, что <tex>L</tex> сводится по Карпу к '''BH<sub>1N</sub>'''. Рассмотрим функцию <tex>f(x) = \langle m, x, 1^{p|x|)}\rangle</tex> по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени <tex>p(|x|)</tex> в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что <tex>x \in L \Leftrightarrow f(x)</tex> ∈ '''BH<sub>1N</sub>'''.
  
 
Пусть <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<sub>1N</sub>''' согласно его определению.
 
Пусть <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<sub>1N</sub>''' согласно его определению.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)