Beweisen, dass wenn

10

Ich würde mich sehr über Ihre Hilfe beim Nachweis des Folgenden freuen.

Wenn dann ist .P = N P.NTime(n100)DTime(n1000)P=NP

Hier ist die Klasse aller Sprachen, die von einer nichtdeterministischen Turing-Maschine in der Polynomzeit von und ist die Klasse aller Sprachen, die von einer deterministischen Turing-Maschine in der Polynomzeit von .O ( n 100 ) D T i m e ( n 1000 ) O ( n 1000 )NTime(n100)O(n100)DTime(n1000)O(n1000)

Hilfe / Anregungen?

Joni
quelle
7
Hinweis: Polsterung .
SDCVVC
Woher kommt diese Frage?
VZN

Antworten:

3

Hier ist die Lösung mit Polsterung. Angenommen, . Definieren Sie eine neue Sprache . Jedes entspricht einem der Länge . Daher können wir entscheiden, ob in nicht deterministischer Zeit , dh . Um zu entscheiden, ob , bilden Sie und führen Sie den -zeitdeterministischen Algorithmus fürL ' = { x 0 | x | 10 - | x | : x L } x L y L | y | = | x | + ( | x | 10 - | x | ) = | x | 10 yLNTime(n1000)L={x0|x|10|x|:xL}xLyL|y|=|x|+(|x|10|x|)=|x|10| x | 1000 = | y | 100 L 'N T i m e ( n 100 ) D T i m e ( n 1000 ) x L y = x 0 x 10 - | x | | y | 1000 = | x | 10000 L ' L yL|x|1000=|y|100LNTime(n100)DTime(n1000)xLy=x0x10|x||y|1000=|x|10000L. Wir schließen daraus, dass .LDTime(n10000)

Yuval Filmus
quelle
2

Teilen Sie das Problem in zwei Teile:

  1. Es gibt eine vollständige Sprache in N T i m e ( n 1000 ) .NPNTime(n1000)
  2. Wenn eine -komplette Sprache ist D T i m e ( n 1000 ) P dann P = N P .NPDTime(n1000)PP=NP
Kaveh
quelle
-2

Dies ist eine nahezu triviale Folge der Definition der NP-Vollständigkeit. Wenn eine Sprache in NP in Polynomzeit lösbar ist (was durch die Prämisse behauptet wird), dann sind sie alle. Eine andere Möglichkeit, dies zu betrachten, besteht darin, den Satz von Cook zur NP-Vollständigkeit zu betrachten , der alle NP-vollständigen Sprachen auf die Erkennung einer Sprache mit SAT und die Umwandlung der nichtdeterministischen Turing-Maschine in SAT reduziert.

vzn
quelle
3
NTime(n100)
nc)c<100
3
c<100
PNP
4
@vzn: Die Frage kann mit der von sdcvvc angedeuteten Auffülltechnik gelöst werden.
Yuval Filmus