P (complessità)
Da Wikipedia, l'enciclopedia libera.
Nella Teoria della complessità computazionale la classe P identifica l'insieme di quei problemi (ovvero linguaggi, insiemi; problemi la cui decisione consiste nella verifica di appartenenza di un dato elemento, o stringa, al linguaggio) decidibili in un numero polinomiale, rispetto alla lunghezza della stringa di input, di passi da una Macchina di Turing deterministica.
È generalmente considerata la classe dei problemi risolvibili in modo "efficiente", dei problemi "trattabili". La classe P, tuttavia, comprende un gran numero di problemi che in termini pratici possono difficilmente essere considerati "trattabili": problemi, ad esempio, per cui il miglior algoritmo disponibile esegue comunque un numero di passi che è un polinomio di grado molto elevato.
| Classi di complessità (elenco) |
|---|
| P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • EXPSPACE • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH |
