Warum verwenden wir keine größeren Klassen, um Determinismus gegen Nichtdeterminismus zu untersuchen?

In einer früheren Frage zur Zeithierarchie habe ich gelernt, dass Gleichheiten zwischen zwei Klassen auf komplexere Klassen und Ungleichungen auf weniger komplexe Klassen übertragen werden können, wobei Argumente mit Auffüllung verwendet werden.

Daher kommt eine Frage in den Sinn. Warum untersuchen wir eine Frage zu verschiedenen Arten von Berechnungen (oder Ressourcen) in der kleinstmöglichen (geschlossenen) Klasse?

Die meisten Forscher glauben, dass . Diese Unterscheidung von Klassen würde nicht zwischen Klassen erfolgen, die denselben Ressourcentyp verwenden. Daher könnte man diese Ungleichheit als universelle Regel betrachten: Der Nichtdeterminismus ist eine mächtigere Ressource. Daher könnte es sich, obwohl es sich um eine Ungleichung handelt, durch Ausnutzung der unterschiedlichen Natur der beiden Ressourcen nach oben verbreiten. Man könnte also auch erwarten . Wenn man diese Beziehung oder eine andere ähnliche Ungleichung beweisen würde, würde dies bedeutenE X P ≠ N E X P P ≠ N $P \neq NP$$EXP \neq NEXP$$P \neq NP$ .

Mein Argument könnte vielleicht in Bezug auf die Physik klar werden. Newton würde es schwer haben, die universelle Schwerkraft zu verstehen, wenn er Steine ​​(Äpfel?) Anstelle von Himmelskörpern untersucht. Das größere Objekt bietet mehr Details in seiner Studie, gibt ein genaueres Modell seines Verhaltens und ermöglicht es, kleinräumige Phänomene zu ignorieren, die möglicherweise irrelevant sind.

Natürlich besteht das Risiko, dass es bei größeren Objekten ein anderes Verhalten gibt, in unserem Fall, dass die zusätzliche Kraft des Nichtdeterminismus in größeren Klassen nicht ausreicht. Was ist, wenn bewiesen ist? Sollten wir am nächsten Tag mit der Arbeit an ?E X P ≠ N E X $P \neq NP$$EXP \neq NEXP$

Halten Sie diesen Ansatz für problematisch? Kennen Sie Forschungsergebnisse, bei denen größere Klassen als Polynome zur Unterscheidung der beiden Berechnungstypen verwendet werden?

Das Problem kann mit und etwas sauberer sein . Der einfachste Weg, über diese Klassen nachzudenken, besteht darin, dass sie mit und identisch sind, jedoch auf unäre Sprachen beschränkt sind. Das heißt, alle Eingaben haben die Form .N E = N t i m e ( 2 O ( n ) ) P N P 1 $E=Dtime(2^{O(n)})$$NE=Ntime(2^{O(n)})$$P$$NP$$1^k$

Das heißt, die Sprache ist genau dann in wenn die Sprache in (Zeichenfolgen mit Zahlen unter Verwendung einer binären Darstellung identifizieren), und in ähnlicher Weise ist isomorph zu unärem .E U L = { 1 x : x ∈ L } P N E N $L$$E$$U_L = \{ 1^x : x\in L \}$$P$$NE$$NP$

Der Versuch, von zu trennen, ist also genauso wie der Versuch, nicht nur von zu trennen , sondern dies tatsächlich in einer unären Sprache zu tun. Kein Grund, es sollte Ihr Leben konzeptionell noch einfacher machen.E P N $NE$$E$$P$$NP$

$P$$NP$$NP$$NP$$P$$P$$NP$

$decidable \neq computability \ enumerable$$NPSpace = PSpace$$primitive \ recursive = nondeterministic \ primitive \ recursive$$P$$NP$$EXP$$NEXP$$P$$NP$$EXP$$NEXP$$E$$NE$

$EXP \neq NEXP$$P \neq NP$$EXP = NEXP$$P$$NP$$P$$NP$