Also known as P class, PTIME, polynomial time, polynomial time class, polynomial complexity class, polynomial complexity, P complexity class
classe di complessità
Wikidata facts
- Instance of
- complexity class
- Subclass of
- computational problem
- Said to be same as
- NP
via Wikidata · CC0
Article · Italiano
Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o (nO(1)), è una delle più importanti classi di complessità. Contiene tutti i problemi decisionali che possono essere risolti da una macchina di Turing deterministica usando una quantità di , o tempo polinomiale. La asserisce che P è la classe di problemi computazionali che sono "risolvibili efficientemente" o "trattabili"; in pratica, qualche problema che non si sa essere in P ha soluzioni pratiche, e qualche problema in P non ne ha.
Abstract from DBpedia / Wikipedia · CC BY-SA