P (Komplexitätsklasse)

In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, die alle Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der „praktisch lösbaren“ Probleme betrachtet.

Eine Verallgemeinerung von P ist die Klasse NP. Die Probleme aus NP sind zwar ebenfalls in Polynomialzeit entscheidbar, jedoch wird hierfür ein nicht realisierbares, nämlich nichtdeterministisches Maschinenmodell eingesetzt. 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.

Formale Definition

Notation:

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \N_0:=\{0,1,2,3,\dots\}} ist die Menge der natürlichen Zahlen mit Null.
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma=\{0,1\}} ist das Alphabet einer formalen Sprache, das heißt jedes Wort ist eine binäre Zeichenfolge bestehend aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} und $1$.
• $\Sigma ^{n}$ bezeichnet die Menge aller binären Wörter der Länge $n\in \mathbb {N} _{0}$.
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma^*=\bigcup_{n \in \N_0} \Sigma^n} bezeichnet die (abzählbare) Menge aller endlich langen binären Wörter.

Ein Entscheidungsproblem kann nun als formale Sprache Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S \subseteq \Sigma^*} dargestellt werden. Jede Probleminstanz wird als Binärstring in $\Sigma ^{*}$ ausgedrückt, und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} enthält genau die Strings, die eine Instanz darstellen, auf die die richtige Antwort „ja“ lautet.

Ein Entscheidungsproblem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S\subseteq \Sigma^*} ist effizient-lösbar, falls ein Algorithmus $A:\Sigma ^{*}\to \{0,1\}$ in Polynomialzeit existiert, so dass für jedes $x$ gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A(x)=1 \iff x\in S.}

Dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf{P}} die Klasse der effizient-lösbaren Entscheidungsprobleme, das heißt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf{P}=\{S:(\exist A )(\forall x)[A(x)=1 \iff x\in S \wedge A \text{ poly}]\}}

Erläuterungen

Ein Algorithmus kann als deterministische Turing-Maschine aufgefasst werden.

Wir haben ein paar Vereinfachungen vorgenommen. Eigentlich meinen wir das Entscheidungsproblem von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} , aber häufig identifiziert man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} mit seinem Entscheidungsproblem. Auch den Begriff des Algorithmus haben wir vereinfacht, da korrekterweise Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} nur die dazugehörige Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_A:\{0,1\}^*\to \{0,1\}\cup \{\bot\}} berechnet, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bot} Fehler bedeutet (es ging etwas schief), mit der das Problem gelöst wird. Wir haben Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_A} identifiziert aber auf den Endzustand $\bot$ verzichtet.

Beziehung zu anderen Komplexitätsklassen

Die folgenden Beziehungen sind bekannt:

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

LOGCFL Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \not=} PSPACE Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \not=} EXPSPACE

P Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \not=} EXPTIME

P-Vollständigkeit

Ein Entscheidungsproblem $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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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)