Die genaue Beziehung zwischen Komplexitätsklassen und Algorithmuskomplexitäten [Duplikat]

Question

Auf diese Frage gibt es hier bereits eine Antwort:

• Was ist die Definition von P, NP, NP-vollständig und NP-hart? 7 Antworten

Gehören alle Algorithmen mit polynomialer Zeitkomplexität zur P-Klasse?Und die P-Klasse hat keinen Algorithmus, der keine polynomielle Komplexität aufweist?

Gehören alle Algorithmen mit nichtpolynomialer Komplexität zu NP oder NP-Schwer oder zu beiden?

Ich versuche nur, den grundlegenden Zusammenhang zu verstehen.

Answer 1

$P$ ist definiert als die Klasse von (Entscheidungs-)Problemen, die über einen Algorithmus verfügen, der sie in polynomieller Zeit löst (in einem TM oder einem polynomial äquivalenten Modell).Somit enthält $P$ genau diese Probleme, nicht mehr und nicht weniger.

Was $NP$ betrifft, ist die Situation heikler.Ein Problem liegt in $NP$, wenn es einen nichtdeterministischen Algorithmus hat, der in polynomieller Zeit läuft.Eine äquivalente, benutzerfreundlichere Definition besteht darin, dass Sie bei gegebener Lösung des Problems deren Korrektheit anhand eines Zeitpolynoms anhand der Größe des Problems überprüfen können.Wenn Sie beispielsweise einen Graphen und einen Pfad angeben, der behauptet, ein Hamilton-Pfad zu sein, können Sie in polynomialer Zeit überprüfen, ob es sich tatsächlich um einen Hamilton-Pfad handelt.Somit liegt das Problem der Entscheidung, ob ein Graph einen Hamilton-Pfad hat, in $NP$.

Klärung:$NP$ ist eine Klasse von Probleme, nicht von Algorithmen.Ein Algorithmus gehört nicht zu $NP$.

Nun ist bekannt, dass einige Probleme keinen polynomialen Zeitalgorithmus haben.Das bedeutet nicht, dass sie sich in $NP$ befinden.Tatsächlich ist bekannt, dass einige Probleme nicht in $NP$ vorkommen.Zum Beispiel jedes $NEXP$-schwere Problem.

Was $NP$-schwere Probleme betrifft – da wir nicht wissen, ob $P=NP$ ist oder nicht, wissen wir nicht, ob jedes Problem außerhalb von $P$ $NP$-schwer ist.Wenn $NP=P$, dann ist jedes Problem $NP$-schwer (außer $\Sigma^*$ und $\emptyset$).

Diese Antwort (die bei weitem unvollständig ist) deckt etwa drei Wochen Material in einem grundlegenden Komplexitätskurs ab.Erwägen Sie vielleicht, ein Lehrbuch wie Sipsers „Theory of Computation“ gründlich zu lesen.

Answer 2

Alle Algorithmen, die ein Entscheidungsproblem in der Polynomzeit lösen, zeigen, dass ihre Probleme in $ P $ liegen. Aber es gibt sicherlich Algorithmen, die keine Polynomzeit für Probleme in $ p $ benötigen. Sie können sortieren, indem Sie alle $ n! $ Permutationen der Input generieren und jeweils prüfen, ob es sortiert ist. Dieser Algorithmus braucht mehr als Exponentialzeit, aber das Problem hat eine Lösung in der Polynomzeit.