P versus NP problem, in full polinomial versus nondeterministic polynomial problem, in computational complexity (un sottocampo di informatica teorica e matematica), la questione se tutti i cosiddetti problemi NP siano in realtà problemi P. Un problema P è uno che può essere risolto in “tempo polinomiale”, il che significa che esiste un algoritmo per la sua soluzione tale che il numero di passaggi nell’algoritmo è limitato da una funzione polinomiale di n, dove n corrisponde alla lunghezza dell’input per il problema., Pertanto, si dice che i problemi P siano facili o trattabili. Un problema è chiamato NP se la sua soluzione può essere indovinata e verificata in tempo polinomiale, e non deterministico significa che non viene seguita alcuna regola particolare per fare l’ipotesi.

I problemi di programmazione lineare sono NP, poiché il numero di passaggi nel metodo simplex, inventato nel 1947 dal matematico americano George Dantzig, cresce esponenzialmente con la dimensione dell’input. Tuttavia, nel 1979 il matematico russo Leonid Khachian scoprì un algoritmo del tempo polinomiale—cioè,, il numero di passi computazionali cresce come una potenza del numero di variabili, piuttosto che esponenzialmente-mostrando così che i problemi di programmazione lineare sono in realtà P. Questa scoperta ha permesso la soluzione di problemi precedentemente intrattabili.

Un problema è NP-difficile se un algoritmo per la sua soluzione può essere modificato per risolvere qualsiasi problema NP—o qualsiasi problema P, del resto, poiché i problemi P sono un sottoinsieme di problemi NP. (Non tutti i problemi NP-hard sono membri della classe dei problemi NP, tuttavia.) Un problema che è sia NP che NP-hard si dice che sia NP-completo., Pertanto, trovare un algoritmo efficiente per qualsiasi problema NP-completo implica che un algoritmo efficiente può essere trovato per tutti i problemi NP, poiché una soluzione per qualsiasi problema appartenente a questa classe può essere riformulata in una soluzione per qualsiasi altro membro della classe., Nel 1971 informatico Americano Stephen Cook ha dimostrato che il satisfiability problema (è un problema di assegnazione di valori alle variabili, in una formula in algebra Booleana tale che l’affermazione è vera) è NP-completo, il primo problema dimostrato di essere NP-completo e aperto la strada a mostrare altri problemi che sono membri della classe di NP-completi problemi. Un famoso esempio di un problema NP-completo è il problema del commesso viaggiatore, che ha ampie applicazioni nell’ottimizzazione degli orari di trasporto., Non è noto se eventuali algoritmi di tempo polinomiale saranno mai trovati per problemi NP-completi, e determinare se questi problemi sono trattabili o intrattabili rimane una delle domande più importanti in informatica teorica. Tale scoperta dimostrerebbe che P = NP = NP-completa e rivoluziona molti campi dell’informatica e della matematica.

Ad esempio, la crittografia moderna si basa sul presupposto che il factoring del prodotto di due grandi numeri primi non sia P., Si noti che verificare il prodotto di due numeri primi è facile (tempo polinomiale), ma calcolare i due fattori primi è difficile. La scoperta di un algoritmo efficiente per il factoring di grandi numeri interromperebbe la maggior parte dei moderni schemi di crittografia.

Nel 2000 il matematico americano Stephen Smale ha ideato un influente elenco di 18 importanti problemi matematici da risolvere nel 21 ° secolo. Il terzo problema sulla sua lista era il problema P contro NP., Anche nel 2000 è stato designato un problema del Millennio, uno dei sette problemi matematici selezionati dal Clay Mathematics Institute di Cambridge, Massachusetts, Stati Uniti, per un premio speciale. La soluzione per ogni problema del Millennio vale $1 milione.