P (Komplexitätsklasse)
in der Komplexitätstheorie eine Komplexitätsklasse / aus Wikipedia, der freien encyclopedia
Liebe Wikiwand-AI, fassen wir uns kurz, indem wir einfach diese Schlüsselfragen beantworten:
Können Sie die wichtigsten Fakten und Statistiken dazu auflisten P (Komplexitätsklasse)?
Fass diesen Artikel für einen 10-Jährigen zusammen
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.