Problema NP
Nella teoria della complessità computazionale, un problema si dice problema NP (nondeterministic polynomial time) quando ogni soluzione al problema può essere verificata in tempo polinomiale.
Ciò significa che, anche se trovare la soluzione potrebbe richiedere un tempo molto lungo, una volta proposta una soluzione, è possibile verificare rapidamente se essa sia corretta o meno.
Questo non implica necessariamente che esista anche un algoritmo in grado di trovare una soluzione.
In altre parole, se una soluzione viene fornita in qualche modo, ad esempio indovinata o generata da un processo non deterministico, possiamo verificare rapidamente se è corretta.
La differenza tra problemi P e NP. L'insieme dei problemi NP include sia problemi per cui conosciamo algoritmi polinomiali (problemi P) sia problemi per i quali non si conoscono ancora degli algoritmi polinomiali in grado di trovare le soluzioni. Quindi, i problemi P sono un sottoinsieme dei problemi NP. $$ P \subset NP $$ L'insieme dei problemi NP include anche i problemi detti NP-completi, quelli per cui se si trovasse un algoritmo polinomiale per risolvere anche solo uno di essi, allora si potrebbero risolvere in tempo polinomiale tutti i problemi in NP.
Esempio
Per capire meglio, facciamo un esempio classico: il problema del commesso viaggiatore (Travelling Salesman Problem, TSP).
In questo problema, dato un elenco di città e le distanze tra ciascuna coppia di città, il compito è trovare il percorso più breve possibile che visita ogni città una volta e ritorna alla città di origine.
Nonostante sia facile verificare se un dato percorso è una soluzione valida (e calcolarne la lunghezza totale), trovare il percorso ottimale può essere estremamente difficile e richiedere molto tempo man mano che il numero di città aumenta.
I problemi NP sono importanti perché comprendono molti problemi pratici in campi come l'ottimizzazione, la crittografia, la pianificazione di risorse, e altro ancora.
Sebbene esistano algoritmi per risolvere questi problemi, molti di essi sono impraticabili su larga scala perché il tempo necessario per trovare una soluzione cresce esponenzialmente con la dimensione del problema.
La questione aperta dei problemi P vs NP. Una grande questione aperta nella scienza informatica è se NP sia equivalente a P, dove P sta per i problemi che possono essere sia risolti che verificati in tempo polinomiale. In altre parole, la domanda è: ogni problema il cui risultato può essere verificato rapidamente può anche essere risolto rapidamente? Questo è noto come il problema P vs NP, ed è uno dei problemi del millennio per il quale non è stata ancora trovata una risposta.
Domande/Risposte
- I problemi P appartengono alla categoria dei problemi NP?
Si, i problemi P sono un sottoinsieme dei problemi NP. Se per un problema NP esiste un algoritmo che non solo verifica ma anche trova una soluzione in tempo polinomiale, allora tale problema appartiene anche alla classe dei problemi P (Polynomial time). Questo vuol dire che tutti i problemi in P sono automaticamente inclusi in NP, dato che se possiamo trovare una soluzione in tempo polinomiale, possiamo certamente verificare una soluzione proposta in tempo polinomiale. - Perché molti problemi NP non hanno algoritmi in grado di risolverli?
Molti problemi in NP non hanno algoritmi noti che li risolvono in tempo polinomiale. Ad esempio, potrebbero esistere degli algoritmi non polinomiali o non esistere affatto. Per questi problemi, la questione se esistano o meno tali algoritmi è aperta e rappresenta una delle questioni centrali nella teoria della complessità computazionale. Per essere problemi NP deve però esistere un algoritmo in grado di verificare se una soluzione, comunque sia stata trovata, è corretta oppure no.
