Beweisen Sie, dass wenn $ mathhrm {ntime} (n^{100}) subseteq mathhrm {dtime} (n^{1000}) $ dann $ mathrm {p} = mathrm {np} $

Question

Ich würde Ihre Hilfe wirklich gerne bei der Beweisung der Folgendes haben.

If $ mathhrm {ntime} (n^{100}) subseteq mathrm {dtime} (n^{1000}) $ dann $ mathrm {p} = mathrm {np} $.

Hier ist $ mathhrm {ntime} (n^{100}) $ die Klasse aller Sprachen, die von nicht deterministischer Turing -Maschine in der Polynomzeit von $ o (n^{100}) $ und $ mathrm {Time entschieden werden kann } (n^{1000}) $ ist die Klasse aller Sprachen, die durch eine deterministische Turing -Maschine in der Polynomzeit von $ o (n^{1000}) $ entschieden werden kann.

Irgendwelche Hilfe/Vorschläge?

Answer 1

Hier ist die Lösung mit Polsterung. Angenommen, $ l in mathhrm {ntime} (n^{1000}) $. Definieren Sie eine neue Sprache $ l '= {x0^{| x |^{10}-| x |}: x in l } $. Jedes $ x in l $ entspricht einigen $ y in l '$ von Länge $ | y | = | x | + (| x |^{10}-| x |) = | x |^{10} $. Daher können wir entscheiden, ob $ y in l '$ in nicht deterministischer Zeit $ | x |^{1000} = | y |^{100} $, dh $ l' in mathrm {ntime} (n^{ 100}) subseteq mathrm {dtime} (n^{1000}) $. Um zu entscheiden, ob $ x in l $, Formular $ y = x0^{x^{10}-| x |} $ und führen Sie die $ | y |^{1000} = | x |^{10000} $ aus -Time Deterministischer Algorithmus für $ l '$. Wir schließen daraus, dass $ l in mathrm {dtime} (n^{10000}) $.

Answer 2

Brechen Sie das Problem in zwei Teile ein:

1. Es gibt eine $ mathsf {np} $-vollständige Sprache in $ mathsf {ntime} (n^{1000}) $.
2. Wenn eine $ mathsf {np} $-vollständige Sprache in $ mathsf {dtime} (n^{1000}) subset mathsf {p} $ dann $ mathsf {p} = mathsf {np} $ ist.

Answer 3

Dies ist eine nahezu triviale Folge der Definition der NP-Vervollständigung. Wenn eine Sprache in NP in der Polynomzeit lösbar ist (was durch die Prämisse behauptet wird), dann sind dies alle. Eine andere Möglichkeit, dies zu betrachten, besteht darin, sich anzusehen Cooks Theorem für die NP-Vervollständigung Dies reduziert alle NP-Complete-Sprachen auf die Erkennung einer Sprache, die SAT und die Umwandlung der nichtdeterministischen Turing-Maschine in SAT beinhaltet.