NP-completezza
Verificato
Aggiornato il 14/08/2026
Significato di «NP-completezza»
Proprietà dei problemi più difficili della classe NP, a cui ogni altro problema di NP può essere ricondotto. Trovare per uno solo di essi un algoritmo efficiente risolverebbe l'intera classe.
Fonti: Un problema è NP-completo se sta in NP ed è NP-hard (ogni problema di NP vi si riduce in tempo polinomiale). CLRS cap. 34; Sipser; Garey-Johnson; Treccani. Verifica web 2026-08-03. · Verificato il 2026-08-03
Domande frequenti su NP-completezza
Cosa significa «NP-completezza»?
Proprietà dei problemi più difficili della classe NP, a cui ogni altro problema di NP può essere ricondotto. Trovare per uno solo di essi un algoritmo efficiente risolverebbe l'intera classe.
A quale glossario appartiene «NP-completezza»?
«NP-completezza» fa parte del glossario Algoritmi e Strutture dati, nella categoria Programmazione di Glossario Italiano.