P (Komplexitätsklasse)
aus Wikipedia, der freien Enzyklopädie
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 (siehe auch P/NP-Problem).
[Bearbeiten] Beziehung zu anderen Komplexitätsklassen
Die folgenden Beziehungen sind bekannt:
- P
EXPTIME
[Bearbeiten] Weblinks
- P im Complexity Zoo (englisch)
