Komplexität #07 - Probleme in NP (3COL und CIRCUIT-SAT)

Wir sehen uns typische Probleme in NP an, also Probleme, die von einer nichtdeterministischen Turingmaschine in polynomieller Zeit gelöst werden können. Zum einen geben wir einen NP-Algorithmus für 3-Färbbarkeit (3COL) an, zum anderen einen NP-Algorithmus für CIRCUIT-SAT, also das Erfüllbarkeitsproblem von Schaltkreisen.

Schließlich kommen wir noch auf das berühmte P-vs-NP-Problem zu sprechen.

[josh]

"NP = Probleme, deren Lösung man effizient verifizieren kann" finde ich sehr greifbar als Beschreibung. Also zum Beispiel beim Traveling Salesman Problem, das ja eigentlich ein Optimierungsproblem ist, wandel ich in ein Entscheidungsproblem um mit der Frage: Gibt es eine Tour in der jede Stadt besucht wird. Eine Tour wird geraten, also ein Weg durch den Graphen, und die Prüfung, ob es sich um eine zulässige Tour handelt ist denkbar einfach. Denn das ist genau dann der Fall, wenn jeder Knoten genau einmal vorkommt (außer Start- & Endknoten->doppelt, da zurückgekehrt wird).
Aber kann ich auch das Entscheidungsproblem aufstellen "Gibt es eine zulässige Tour, die optimal ist" oder "Gibt es eine Tour, die kürzer als 200km ist"? Wenn ja, würde sich was ändern? Die bisherigen Probleme scheinen ja nicht nur zu fragen, ob es überhaupt eine zulässige Lösung gibt.

[queenpost]

Hallo!
Weswegen sind 10 Videos der Playlist "nicht verfügbar"??