NP-hard
Verificato
Aggiornato il 14/08/2026
Significato di «NP-hard»
Categoria di problemi almeno tanto difficili quanto i più ardui della classe NP, senza dover appartenere a NP stessi. Per essi non si conoscono algoritmi efficienti, e spesso ci si accontenta di soluzioni approssimate.
Fonti: Un problema è NP-hard se ogni problema di NP vi si riduce in tempo polinomiale; non deve necessariamente stare in NP. CLRS cap. 34; Garey-Johnson; Treccani. Verifica web 2026-08-03. · Verificato il 2026-08-03
Domande frequenti su NP-hard
Cosa significa «NP-hard»?
Categoria di problemi almeno tanto difficili quanto i più ardui della classe NP, senza dover appartenere a NP stessi. Per essi non si conoscono algoritmi efficienti, e spesso ci si accontenta di soluzioni approssimate.
A quale glossario appartiene «NP-hard»?
«NP-hard» fa parte del glossario Algoritmi e Strutture dati, nella categoria Programmazione di Glossario Italiano.