Classe P
Verificato
Aggiornato il 10/09/2026
Significato di «Classe P»
In teoria della complessità è l'insieme dei problemi decisionali risolvibili da una macchina di Turing deterministica in tempo polinomiale rispetto alla dimensione dell'input. Rappresenta i problemi considerati trattabili in modo efficiente ed è al centro della questione aperta P contro NP.
Fonti: Sipser, Introduction to the Theory of Computation; Wikipedia EN P (complexity) · Verificato il 2026-09-10
Domande frequenti su Classe P
Cosa significa «Classe P»?
In teoria della complessità è l'insieme dei problemi decisionali risolvibili da una macchina di Turing deterministica in tempo polinomiale rispetto alla dimensione dell'input. Rappresenta i problemi considerati trattabili in modo efficiente ed è al centro della questione aperta P contro NP.
A quale glossario appartiene «Classe P»?
«Classe P» fa parte del glossario Fondamenti di informatica, nella categoria Informatica di Glossario Italiano.