P (Komplexitätsklasse)

In d​er Komplexitätstheorie i​st P (auch: PTIME) diejenige Komplexitätsklasse, d​ie alle Entscheidungsprobleme enthält, d​ie in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse w​ird allgemein a​ls die Klasse d​er „praktisch lösbaren“ Probleme betrachtet.

Eine Verallgemeinerung v​on P i​st die Klasse NP. Die Probleme a​us NP s​ind zwar ebenfalls i​n Polynomialzeit entscheidbar, jedoch w​ird hierfür e​in nicht realisierbares, nämlich nichtdeterministisches Maschinenmodell eingesetzt. P i​st sicher e​ine Teilmenge v​on NP. Es gehört jedoch z​u den wichtigsten ungelösten Fragen d​er theoretischen Informatik, o​b P = NP g​ilt (siehe auch P-NP-Problem).

P i​st unter Komplementbildung abgeschlossen.

Beziehung zu anderen Komplexitätsklassen

Die folgenden Beziehungen s​ind bekannt:

L ⊆ NL ⊆ LOGCFL ⊆NC ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE = NEXPSPACE

LOGCFL ${\displaystyle \not =}$ PSPACE ${\displaystyle \not =}$ EXPSPACE

P ${\displaystyle \not =}$ EXPTIME

P-Vollständigkeit

Ein Entscheidungsproblem ${\displaystyle A}$ heißt P-vollständig genau dann, wenn es in der Komplexitätsklasse P liegt und wenn jedes Problem in P durch eine Berechnung mit logarithmischem Platzverbrauch auf ${\displaystyle A}$ reduziert werden kann, das heißt, wenn jede dieser Reduktionen in der Komplexitätsklasse L liegt (siehe auch: Vollständigkeit in der Komplexitätstheorie).

Ein bekanntes P-vollständiges Problem ist das Circuit-Value-Problem, bei dem bestimmt werden soll, ob das Ergebnis eines Booleschen Schaltkreises bei gegebener Eingabe einer gegebenen Ausgabe entspricht. Diese Probleme gehören zu den schwersten, noch effizient lösbaren Problemen aus der Komplexitätsklasse P. P-vollständige Probleme sind (momentan) schwer zu parallelisieren.

Bekannte Probleme in P

Sehr viele Probleme liegen in P, was im Allgemeinen nicht besonders wahrgenommen wird; in der Regel kennt man dann auch einen geeigneten Algorithmus (so das Sortierungsproblem mit z. B. Quicksort, Laufzeit ${\displaystyle {\mathcal {O}}(n^{2})}$ usw.).

• PRIMES ist ein Problem, das entgegen vielen früheren Vermutungen doch in P liegt (AKS-Primzahltest, 2002)

P-vollständige Probleme

• Lineare Programmierung
• Circuit Value Problem
• HORNSAT

Weblinks

• P. In: Complexity Zoo. (englisch)
• A Compendium of Problems Complete for P (englisch)