Wie viele NP vollständige Probleme gibt es?

Inhaltsverzeichnis:

1. Wie viele NP vollständige Probleme gibt es?
2. Wann ist ein Problem NP?
3. Wann liegt ein Problem in NP?
4. Ist P Teilmenge von NP?
5. Ist P unter Komplement abgeschlossen?

Wie viele NP vollständige Probleme gibt es?

Karps 21 NP-vollständige Probleme ist eine in der Komplexitätstheorie gebräuchliche Menge NP-vollständiger Rechenprobleme.

Wann ist ein Problem NP?

Nach einer alternativen Definition ist ein Entscheidungsproblem genau dann in NP, wenn eine gegebene Lösung für das entsprechende Suchproblem von einer deterministischen Turingmaschine in Polynomialzeit überprüft werden kann.

Wann liegt ein Problem in NP?

Nach einer alternativen Definition ist ein Entscheidungsproblem genau dann in NP, wenn eine gegebene Lösung für das entsprechende Suchproblem von einer deterministischen Turingmaschine in Polynomialzeit überprüft werden kann.

Ist P Teilmenge von NP?

P ist sicher eine Teilmenge von NP. Es gehört jedoch zu den wichtigsten ungelösten Fragen der theoretischen Informatik, ob P = NP gilt (siehe auch P-NP-Problem). P ist unter Komplementbildung abgeschlossen.

Ist P unter Komplement abgeschlossen?

Das genügt, da jede Sprache aus NP auf L′ reduzierbar ist und wegen L′ ≼ L dann auch auf L. Hierfür häufig verwendet: SAT-Problem, d.h. Frage: Ist NP abgeschlossen unter Komplementbildung? Antwort: Keiner weiß es!