Доказательство того, что если то

10

Мне очень нужна ваша помощь в доказательстве следующего.

Если то . P = N PNTime(n100)DTime(n1000)P=NP

Здесь - это класс всех языков, которые могут быть определены недетерминированной машиной Тьюринга за полиномиальное время и - это класс всех языков, которые могут быть определены детерминированной машиной Тьюринга за полиномиальное время .O ( n 100 ) D T i m e ( n 1000 ) O ( n 1000 )NTime(n100)O(n100)DTime(n1000)O(n1000)

Любая помощь / предложения?

Joni
источник
7
Подсказка: отступы .
sdcvvc
откуда этот вопрос?
vzn

Ответы:

3

Вот решение с использованием отступов. Предположим, что . Определите новый язык . Каждому соответствует некоторый длины . Поэтому мы можем решить, будет ли в недетерминированное время , то есть . Чтобы решить, будет ли , сформировать и запустить детерминистский алгоритм | времениL = { x 0 | х | 10 - | х | : x L } x L y L | у | = | х | + ( | x | 10 - | x | ) = | х | 10 летLNTime(n1000)L={x0|x|10|x|:xL}xLyL|y|=|x|+(|x|10|x|)=|x|10| х | 1000 = | у | 100 L N T i m e ( n 100 ) D T i m eyL|x|1000=|y|100x L y = x 0 x 10 - | х | | у | 1000 = | х | 10000 L L LNTime(n100)DTime(n1000)xLy=x0x10|x||y|1000=|x|10000L, Мы заключаем, что .LDTime(n10000)

Юваль Фильмус
источник
2

Разбейте проблему на две части:

  1. В есть -комплектный язык .N T i m e ( n 1000 )NPNTime(n1000)
  2. Если -комплектный язык находится в то .D T i m e ( n 1000 ) P P = N PNPDTime(n1000)PP=NP
Кава
источник
-2

Это почти тривиальное следствие определения NP-полноты. Если какой-либо язык в NP разрешим за полиномиальное время (что утверждается предпосылкой), то все они. Еще один способ взглянуть на это - взглянуть на теорему Кука о NP-полноте, которая сводит все NP-завершенные языки к распознаванию языка, включающего SAT, и преобразованию недетерминированной машины Тьюринга в SAT.

ВЗН
источник
3
То, что вы сказали, правда, но для NP-полных языков (не для NP-языков). Мы также должны показать, что существует NP-полный язык, разрешимый в -правде, я думаю, но не очевидный по определению. NTime(n100)
SamM
согласился, хорошо. думаю, что это следует из границ в доказательстве Кука ....? все NP-машины могут быть преобразованы / решены с помощью SAT в NTime ( , ...? c < 100nc)c<100
vzn
3
@ VZN: Я не думаю, что мы можем доказать . Я полагаю, что вы можете противоречить одной из теорем иерархии ...c<100
Aryabhata
немного подумав об этом, согласитесь. (первый взгляд, думал, что это был основной вопрос ...) Приготовление доказательства создает новый SAT, полиномиально ограниченный по размеру по сравнению с исходной машиной, но начальная машина не ограничена по показателю полинома (по отношению к этому доказательству). если я выведу противоречие, то =) ... в любом случае, может быть, мы говорим, что это на самом деле открытый вопрос? то есть не известно, чтобы быть правдой или ложью относительно существующей теории? PNP
vzn
4
@vzn: Вопрос может быть решен с использованием техники заполнения, на которую ссылается sdcvvc.
Юваль Фильмус