Wenn die untere Grenze eines Problems exponentiell ist, ist es dann NP?

Unter der Annahme , dass wir ein Problem haben , und wir zeigten , dass die für die Lösung gebunden unteren ist . $p$ $p$ $\mathcal{\Omega}(2^n)$

Kann die untere Schranke das Problem in implizieren ? $\mathcal{\Omega}(2^n)$ $NP$

time-complexity np-complete Kelalaka
quelle

Es ist kein NP, aber es ist NP-schwer.

user35734

Woher weißt du, dass es NP-schwer ist?

Yuval Filmus

Wenn Sie ein Problem sowohl in

als auch in NP zeigen könnten , hätten Sie P

NP bewiesen .

Ω (2^{n})

$\mathcal{\Omega}(2^n)$

\neq

$\neq$

Kasperd

@kasperd: Wir nennen das Merkle's Puzzles, aber es sollte aus P =? NP ausgeschlossen werden, da die spezifische Form keine andere mit den gleichen Eigenschaften ergibt und ein sonstiger Beweis von P = NP wahrscheinlich jegliche Möglichkeit beseitigt, Merkle's Puzzles herzustellen, die tatsächlich so funktionieren beabsichtigt. Die exponentielle Zeit Merkles Puzzles ist auch PSPACE für den vorgesehenen Benutzer.

Joshua

@Joshua Merkles Rätsel sind in Abhängigkeit von der Eingabelänge nicht exponentiell . (Nun, wenn wir annehmen, dass die Lösung für Alice polynomial ist).

Rus9384

Antworten:

Nein. Zum Beispiel hat das Halteproblem eine untere Grenze von $\Omega(2^n)$ , aber es liegt nicht in NP vor (da es nicht berechenbar ist).

Der nichtdeterministische Zeithierarchiesatz zeigt, dass jedes NEXP-vollständige Problem ein weiteres Beispiel ist (wobei $2^n$ möglicherweise durch eine kleinere Exponentialfunktion $c^{n^\epsilon}$ ).

NP ist eine Obergrenze für die Komplexität eines Problems.

Yuval Filmus
quelle

Könnten Sie ein Beispiel für ein Problem geben, das

aber nicht NP-hart ist?

Ω (2^{n})

$\Omega(2^n)$

Mario Carneiro

Sie können ein solches Problem mithilfe der Diagonalisierung konstruieren.

Yuval Filmus

Entschuldigung, ich folge nicht. Was wird diagonalisiert? Zählen wir Probleme oder Algorithmen auf? Wie folgt die Nicht-NP-Härte?

Mario Carneiro

Sie zählen sowohl Turing-Maschinen mit einer Laufzeit von

als auch polynomielle Zeitreduzierungen auf und stellen dabei sicher, dass keine der ersteren Ihre Sprache berechnet und keine der letzteren SAT auf Ihre Sprache reduziert.

2^{n}

$2^n$

Yuval Filmus

Erstens, wie Yuval betont , könnte das Problem viel schwieriger sein als die von Ihnen nachgewiesene Untergrenze.

Zweitens wissen wir nicht, wie sich das Problem auf bezieht , selbst wenn die Lösung Zeit $\Theta(2^n)$ in Anspruch nimmt . Es ist möglich, dass , in welchem Fall ein Problem in nach dem Zeithierarchiesatz sicherlich nicht in ist. Aber selbst wenn , ist es möglich , dass das Problem exponentiell Raum benötigt , so ist nicht in . $\mathbf{NP}$ $\mathbf{P}=\mathbf{NP}$ $\mathrm{TIME}[\Omega(2^n)]$ $\mathbf{NP}$ $\mathbf{P}\neq\mathbf{NP}$ $\mathbf{NP}$

Die besten Algorithmen, die wir für $\mathbf{NP}$ -komplette Probleme kennen, benötigen exponentielle Zeit, aber Sie sollten nicht davon ausgehen, dass "in $\mathbf{NP}$ " "exponentielle Zeit benötigt" oder umgekehrt.

David Richerby
quelle