Problema NP-completo
Verificato
Aggiornato il 10/09/2026
Significato di «Problema NP-completo»
Problema di decisione che appartiene alla classe NP ed è al tempo stesso NP-arduo: ogni altro problema di NP vi si riduce in tempo polinomiale. Sono i più difficili di NP e se ne esistesse un algoritmo polinomiale seguirebbe P=NP; esempi classici sono la soddisfacibilità booleana e il commesso viaggiatore.
Fonti: Cormen et al., Introduction to Algorithms (MIT Press); Wikipedia NP-completeness · Verificato il 2026-09-10
Domande frequenti su Problema NP-completo
Cosa significa «Problema NP-completo»?
Problema di decisione che appartiene alla classe NP ed è al tempo stesso NP-arduo: ogni altro problema di NP vi si riduce in tempo polinomiale. Sono i più difficili di NP e se ne esistesse un algoritmo polinomiale seguirebbe P=NP; esempi classici sono la soddisfacibilità booleana e il commesso viaggiatore.
A quale glossario appartiene «Problema NP-completo»?
«Problema NP-completo» fa parte del glossario Fondamenti di informatica, nella categoria Informatica di Glossario Italiano.