Die Klassen P und NP

Sollten Begriffe unklar sein siehe Beitrag Glossar.

Nicht-deterministische Algorithmen mit polynomialer Komplexität

Wenn wir bisher von Algorithmen gesprochen haben, haben wir vorausgesetzt, dass der Algorithmus deterministisch in dem Sinne ist, das der nächste Ausführungsschritt immer genau feststeht. Wenn man diese Voraussetzung weglässt, gelangt man zu den nichtdeterministischen Algorithmen.

Etliche Probleme mit noch nicht geklärter Komplexität lassen sich mit nichtdeterministischen Algorithmen lösen, die eine polynomiale Komplexität haben. Nichtdeterministische Algorithmen sind nicht auf realen Rechnern realisierbar (Stand 2019).

Die Menge der Entscheidungsprobleme mit polynomiell Zeit beschränkten nichtdeterministischen Algorithmen wird als NP bezeichnet. Die Menge der Entscheidungsprobleme mit polynomiell Zeit beschränkten deterministischen Algorithmen wird als P bezeichnet. Die Frage ob die Komplexitätsklassen P und NP gleich oder verschieden sind, ist als P-NP-Problem bekannt und gehört zu den wichtigsten offenen Fragen der theoretischen Informatik.

NP-vollständige Probleme

Ein Entscheidungsproblem ist NP-vollständig, wenn es

  • in der Komplexitätslasse NP liegt: Ein deterministisch arbeitender Rechner benötigt nur polynomiell viel Zeit, um zu entscheiden, ob eine vorgeschlagene Lösung eines zugehörigen Suchproblems tatsächlich eine Lösung ist, und
  • wenn jedes Problem P aus NP auf P* reduzierbar ist

Eine wesentliche Eigenschaft von NP-vollständigen Problemen ist, dass ihre Lösung auf realen Rechnern viel Zeit in Anspruch nimmt.

  1. für kein NP-vollständiges Problem ist bisher nachgewiesen, dass es in polynomieller Zeit lösbar wäre
  2. falls nur ein NP-vollständiges Problem in polynomieller Zeit lösbar wäre, dann wäre jedes Problem aus der Komplexitätsklasse NP lösbar

Problemreduktion

Bei der Reduktion werden ausschließlich Entscheidungsprobleme von Mengen natürlicher Zahlen betrachtet. Das Ziel ist also stets, die charakteristische Funktion x einer Teilmenge von natürlichen Zahlen zu berechnen. Dieser Ansatz hat den Vorteil, dass nun die Probleme mit den Teilmengen selbst identifiziert werden können.

Eine Polynomialzeitreduktion ist eine spezielle Form der Reduktion in der theoretischen Informatik. Zusätzlich zur Reduzierbarkeit wird gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomielle many-one Reduktionen werden in der Komplexitätstheorie verwendet, um nachzuweisen, dass ein Algorithmus der Komplexitätsklasse NP auch NP-vollständig ist.

SAT

SAT (eng. satisfiabillity; Erfüllbarkeit) ist eine Variante des Erfüllbarkeitsproblems der Aussagenlogik. Nach dem Satz von Cook ist SAT ein NP-vollständiges Problem. Cook hat bewiesen, dass man alle NP Probleme auf SAT reduzieren kann.

SAT lässt sich in das Cliquenproblem und das Rucksackproblem polynomiell reduzieren.

Demnach ist SAT ein Problem von dem bewiesen wurde, dass man alle NP-Probleme darauf reduzieren kann, ohne alle NP-Probleme zu kennen. Ein Problem P ist auf ein höher gestelltes Problem P* reduzierbar, wenn Problem P mit Problem P* lösbar ist.

Schreibe einen Kommentar