Classe NP
Verificato
Aggiornato il 10/09/2026
Significato di «Classe NP»
In teoria della complessità, classe dei problemi decisionali la cui soluzione, una volta fornita, e verificabile in tempo polinomiale da una macchina di Turing deterministica (ovvero risolvibili in tempo polinomiale da una macchina non deterministica). Include P; se P sia uguale a NP resta un problema aperto.
Fonti: Sipser, Introduction to the Theory of Computation; Wikipedia EN, NP (complexity) · Verificato il 2026-09-10
Domande frequenti su Classe NP
Cosa significa «Classe NP»?
In teoria della complessità, classe dei problemi decisionali la cui soluzione, una volta fornita, e verificabile in tempo polinomiale da una macchina di Turing deterministica (ovvero risolvibili in tempo polinomiale da una macchina non deterministica). Include P; se P sia uguale a NP resta un problema aperto.
A quale glossario appartiene «Classe NP»?
«Classe NP» fa parte del glossario Fondamenti di informatica, nella categoria Informatica di Glossario Italiano.