Does

Does bedeuten ? $\mathsf{EXP}=\mathsf{NEXP}$ $\mathsf{E}=\mathsf{NE}$

cc.complexity-theory conditional-results nexp structural-complexity Argentpepper
quelle

Ja, E = NE impliziert EXP = NEXP, was mit einem Auffüllargument bewiesen werden kann.

Mohammad Al-Turkistany

Mir ist nicht klar, warum EXP = NEXP E = NE impliziert. Wenn dies wahr wäre, könnte jeder

-Zeit-Algorithmus für Succinct3SAT in einen

-Zeit-Algorithmus für Succinct3SAT konvertiert werden. Vielleicht haben Sie die Dinge umgekehrt und wollten nach den anderen Implikationen fragen?

2^{n^{k}}

$2^{n^k}$

2^{O (n)}

$2^{O(n)}$

Ryan Williams

Und dann ist P = NP, wenn P = 0 oder N = 1!

Daniel Apon

Ja. Ich denke, es ist ein Hausaufgabenproblem.

Mohammad Al-Turkistany

Ich verstehe den Abschluss dieser Frage nicht als „keine echte Frage“, nachdem sie zu einer vernünftigen Frage bearbeitet wurde (obwohl der Wortlaut der Frage nicht interessant ist). Zum Beispiel kann der Kommentar von Ryan Williams eine Antwort darauf sein.

Tsuyoshi Ito

Does

Antworten: