Un problema NP-hard è un problema sì/no in cui trovare una soluzione per esso è difficile almeno quanto trovare una soluzione per il problema più difficile la cui soluzione può essere rapidamente verificata come se fosse vera. Alcuni problemi NP-hard sono quelli in cui una soluzione funzionante può essere verificata rapidamente (problemi NP) e altri no. I problemi NP-hard che sono anche problemi NP rientrano in una categoria chiamata NP-complete.
Un esempio di un problema che è difficile da risolvere almeno quanto qualsiasi altro problema per il quale possiamo verificare rapidamente le soluzioni, che è anche rapidamente verificabile (è sia NP-hard che NP):
Un commesso viaggiatore vuole visitare 100 città guidando, iniziando e terminando il suo viaggio a casa. Ha una scorta limitata di benzina, quindi può guidare solo per un totale di 10.000 chilometri. Vuole sapere se può visitare tutte le città senza rimanere senza benzina.
La gente non sa come risolvere questo problema più velocemente che testando ogni possibile risposta, ma se si trova una soluzione che permette al venditore di farlo, possiamo usare un algoritmo per verificare che sia vero. Questo problema è noto anche come problema del commesso viaggiatore.
Un esempio di un problema che è difficile da risolvere almeno quanto qualsiasi altro problema per il quale possiamo verificare rapidamente le soluzioni, ma che non può essere controllato rapidamente (è NP-duro, ma non è NP):
se qualcuno avvia un programma che semplicemente va,
mentre (true){ continua; }
e non si ferma mai, funzionerà per sempre?
Non esiste un modo noto per trovare una soluzione a tutti i problemi di questo tipo, e anche questo non può essere controllato.
Domande e risposte
D: Che cos'è un problema NP-hard?
R: Un problema NP-hard è un tipo di problema matematico utilizzato nell'informatica che è un problema sì/no in cui trovare una soluzione è almeno altrettanto difficile che trovare una soluzione per il problema più difficile la cui soluzione può essere rapidamente verificata come vera.
D: È possibile verificare rapidamente una soluzione funzionante per tutti i problemi NP-hard?
R: No, solo alcuni problemi NP-hard, chiamati problemi NP, hanno soluzioni che possono essere verificate rapidamente.
D: Come si chiama la categoria dei problemi NP-hard che sono anche problemi NP?
R: I problemi difficili NP che sono anche problemi NP rientrano in una categoria chiamata NP-completa.
D: Tutti i problemi NP-hard sono NP-completi?
R: No, non tutti i problemi NP-hard sono NP-completi. Solo quelli che sono anche problemi NP rientrano in questa categoria.
D: I problemi NP-hard sono facili da risolvere?
R: No, i problemi NP-hard non sono facili da risolvere. Infatti, trovare una soluzione è almeno altrettanto difficile che trovare una soluzione per il problema più difficile, la cui soluzione può essere rapidamente verificata come vera.
D: Ci sono dei vantaggi nel risolvere i problemi NP-hard?
R: Sì, la soluzione di problemi NP-hard può offrire vantaggi in vari campi, come l'informatica, la fisica e le scienze sociali, in quanto possono richiedere calcoli e modelli complessi.
D: C'è una ricerca in corso sulla risoluzione di problemi NP-hard?
R: Sì, la ricerca sulla soluzione dei problemi NP-hard è in corso, in quanto questi problemi continuano ad essere rilevanti in vari campi e trovare algoritmi e soluzioni efficienti può avere implicazioni significative.
