Also known as P class, PTIME, polynomial time, polynomial time class, polynomial complexity class, polynomial complexity, P complexity class
in der Komplexitätstheorie eine Komplexitätsklasse
Wikidata facts
- Instance of
- complexity class
- Subclass of
- computational problem
- Said to be same as
- NP
via Wikidata · CC0
Article · Deutsch
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.
Abstract from DBpedia / Wikipedia · CC BY-SA