La questione se P equivale a P NP è una delle questioni aperte più importanti nell' informatica teorica a causa delle ampie implicazioni di una soluzione. Se la risposta è sì, si possono dimostrare che molti problemi importanti hanno soluzioni più efficienti. Questi includono vari tipi di problemi di programmazione integer nella ricerca sulle operazioni, molti problemi nella logistica, previsione della struttura proteica in biologia e la capacità di trovare prove formali di teoremi matematici puri. Il problema P contro NP è uno dei problemi del Premio del Millennio proposto dal Clay Mathematics Institute. C' è un premio di 1.000.000.000 di dollari per risolvere il problema.
Qual è il problema particolare della biologia che trarrebbe vantaggio dal determinare che P = NP?
previsione della struttura proteica previsione della struttura proteica previsione della struttura proteica