Folgen des Nichtdeterminismus beschleunigen die deterministische Berechnung

Wenn $\mathsf{NP}$ eine Klasse von Superpolynomzeitproblemen enthält, d.h.

für eine Funktion $t \in n^{\omega(1)}$ ist $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$ ,

$\mathsf{P} \subsetneq \mathsf{NP}$

Aber gibt es noch andere interessante Konsequenzen, die nicht trivial sind (dh keine Konsequenz von ), wenn Nichtdeterminismus deterministische Berechnungen beschleunigen kann?$\mathsf{P} \subsetneq \mathsf{NP}$

Ich habe eine verwandte Konsequenz gefunden.

, enthält , wobei . Es stellt sich heraus, dass dies gerade genug Zeit ist, um gegen zu diagonalisieren . Erstellen Sie insbesondere die folgende Maschine:$NEXP$$DTIME(2^{O(t)})$$t = n^{\omega(1)}$$P/poly$

Bei der Eingabe der Länge , betrachtet die Turingmaschine . Für jedes mögliche Beratung String der Länge und jeden möglichen bitstring der Länge , lief auf mit Rat , und lehnt nach Schritten , wenn Sie noch nicht angenommen haben. Notieren Sie Ihre Ergebnisse in einer Tabelle. Diese Prozedur wird in .$x$$n$$n^{th}$$M$$t$ $b$$n$$M$$b$$a$$t$$DTIME(2^{O(t)})$

Wenn bei Eingabe mindestens die Hälfte der Hinweiszeichenfolgen dazu führen, dass , definieren wir es stattdessen als korrekt, damit unser Algorithmus es akzeptiert (andernfalls ist es korrekt , wenn unser Algorithmus ablehnt). Jede Beratung Strings , die verursacht zu bekommen falsch (das heißt, zumindest die Hälfte Ratschläge Strings) jetzt bekommen geworfen aus dem Tisch. Wir wiederholen dann den Vorgang bei Eingabe : Wenn mindestens die Hälfte der überlebenden Hinweiszeichenfolgen dazu führen, dass wird, akzeptiert unser Algorithmus (und lehnt andernfalls ab). Fahren Sie so für alle Eingaben der Länge (obwohl wirklich nur$0^n$$M$$M$$0^n$$0^{n-1}1$$M$$n$$t$ von ihnen werden benötigt - nach so vielen Eingaben haben wir alle möglichen Ratschläge weggeworfen).

Diese Sprache kann eindeutig in , von dem wir angenommen haben, dass es sich um . Andererseits kann es nicht in : Der Satz von Eingaben der Länge diagonalisiert gegen die Aussicht, dass zur Entscheidung der Sprache verwendet wird.$DTIME(2^{O(t)})$$NEXP$$P/Poly$$n$$M_n$

Wir erhalten also , was interessant wäre.$NEXP \not \subset P/poly$

Ich werde die Frage offen lassen, falls sich jemand etwas anderes einfallen lässt.