NP-completezza
Verificato
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