P (Komplexitätsklasse)

Grundidee und Bedeutung

P, auch PTIME genannt, ist eine Komplexitätsklasse der theoretischen Informatik. Sie enthält alle Entscheidungsprobleme, die eine deterministische Turingmaschine in Polynomialzeit lösen kann. Ein Entscheidungsproblem verlangt als Ergebnis nur „ja“ oder „nein“. Polynomialzeit bedeutet, dass die Laufzeit durch ein Polynom in der Länge der Eingabe begrenzt ist. P gilt deshalb allgemein als die Klasse der „praktisch lösbaren“ beziehungsweise effizient lösbaren Probleme.

P ist unter Komplementbildung abgeschlossen: Liegt ein Entscheidungsproblem in P, dann liegt auch das Problem in P, bei dem die Ja- und Nein-Antworten vertauscht werden.

Formale Definition

Für die formale Beschreibung gilt:

• ℕ₀ := {0, 1, 2, 3, …} ist die Menge der natürlichen Zahlen einschließlich null.

• Σ = {0, 1} ist ein Alphabet. Jedes Wort über diesem Alphabet ist eine binäre Zeichenfolge aus 0 und 1.

• Σⁿ bezeichnet die Menge aller binären Wörter der Länge n ∈ ℕ₀.

• Σ* = ⋃ₙ∈ℕ₀ Σⁿ ist die abzählbare Menge aller endlich langen binären Wörter.

Ein Entscheidungsproblem wird als formale Sprache S ⊆ Σ* dargestellt. Jede Probleminstanz wird durch einen Binärstring beschrieben. S enthält genau diejenigen Strings, für deren Instanzen die richtige Antwort „ja“ lautet.

S heißt effizient lösbar, wenn ein Algorithmus A: Σ* → {0, 1} existiert, der in Polynomialzeit arbeitet und für jedes x die Bedingung

A(x) = 1 ⇔ x ∈ S

erfüllt. Damit ist

P = {S : (∃A)(∀x)[A(x) = 1 ⇔ x ∈ S ∧ A poly]}.

Dabei bedeutet „A poly“, dass A eine polynomielle Laufzeit besitzt.

Modell und vereinfachte Schreibweise

Ein Algorithmus kann hier als deterministische Turingmaschine aufgefasst werden: Für dieselbe Eingabe ist der Berechnungsablauf eindeutig festgelegt.

Die Definition verwendet einige übliche Vereinfachungen. Genau genommen ist vom Entscheidungsproblem der Sprache S die Rede; häufig werden jedoch die Sprache und ihr Entscheidungsproblem miteinander identifiziert. Ebenso wird der Algorithmus A mit der von ihm berechneten Funktion f_A: {0,1}* → {0,1} ∪ {⊥} gleichgesetzt. Das Symbol ⊥ bezeichnet einen Fehlerzustand, also den Fall, dass etwas schiefgegangen ist. In der vereinfachten Definition wird dieser Fehlerzustand weggelassen.

Einordnung unter andere Klassen

NP ist eine Verallgemeinerung von P. Probleme aus NP sind auf einem nichtdeterministischen Maschinenmodell in Polynomialzeit entscheidbar. Dieses Modell gilt nicht als realisierbares gewöhnliches Rechenmodell. Sicher ist P ⊆ NP. Ob sogar P = NP gilt, ist unbekannt und gehört als P-NP-Problem zu den wichtigsten ungelösten Fragen der theoretischen Informatik.

Bekannt ist die folgende Kette von Inklusionen:

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

Eine Inklusion bedeutet, dass jedes Problem der links stehenden Klasse auch zur rechts stehenden Klasse gehört. Einige Klassen sind nachweislich verschieden:

LOGCFL ≠ PSPACE ≠ EXPSPACE

und

P ≠ EXPTIME.

Die Kette allein sagt dagegen nicht, dass alle benachbarten Klassen verschieden sind.

P-vollständige und bekannte Probleme

Ein Entscheidungsproblem A heißt P-vollständig, wenn zwei Bedingungen erfüllt sind: Erstens liegt A selbst in P. Zweitens lässt sich jedes Problem aus P mit logarithmischem Platzverbrauch auf A reduzieren; diese Reduktionen liegen also in der Komplexitätsklasse L. Eine Reduktion überführt Instanzen eines Problems in Instanzen eines anderen Problems, sodass dessen Lösung zur Lösung des ursprünglichen Problems verwendet werden kann.

P-vollständige Probleme gehören zu den schwersten Problemen, die innerhalb von P noch effizient lösbar sind. Nach heutigem Kenntnisstand sind sie schwer zu parallelisieren, also schwer so aufzuteilen, dass viele Rechenschritte gleichzeitig ausgeführt werden können. Genannte Beispiele sind:

• Circuit Value Problem: Es wird bestimmt, ob das Ergebnis eines Booleschen Schaltkreises bei einer gegebenen Eingabe einer gegebenen Ausgabe entspricht.

• Lineare Programmierung.

• HORNSAT.

Sehr viele weitere Probleme liegen in P. Häufig ist für sie ein passender Algorithmus bekannt. Als Beispiel nennt der Artikel das Sortierungsproblem, das etwa mit Quicksort in einer Laufzeit von O(n²) bearbeitet werden kann. Auch PRIMES, die Entscheidung, ob eine Zahl eine Primzahl ist, liegt entgegen früheren Vermutungen in P. Dies zeigt der AKS-Primzahltest aus dem Jahr 2002.