P (Komplexitätsklasse)

In der Komplexitätstheorie ist P diejenige Komplexitätsklasse, welche die 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 auch NP eine Teilmenge von P ist und somit, ob P=NP gilt.

Beziehung zu anderen Komplexitätsklassen

Die folgenden Beziehungen sind bekannt:

NC ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME

Weblinks

• P im Complexity Zoo (englisch)

See also: P (Komplexitätsklasse), BPP (Komplexitätsklasse), BQP (Komplexitätsklasse), EXPTIME, E (Komplexitätsklasse), Entscheidungsproblem