p versus NP problem, i full polynom kontra nondeterministic polynom problem, i beräkningskomplexitet (ett delfält av teoretisk datavetenskap och matematik), frågan om alla så kallade NP problem är faktiskt P problem. Ett P-problem är ett som kan lösas i ”polynomial tid”, vilket innebär att en algoritm existerar för sin lösning så att antalet steg i algoritmen begränsas av en polynomial funktion av n, där n motsvarar längden på ingången för problemet., Således, p problem sägs vara lätt, eller tractable. Ett problem kallas NP om dess lösning kan gissas och verifieras i polynom tid, och nondeterministic innebär att ingen särskild regel följs för att göra gissningen.

linjära programmeringsproblem är NP, eftersom antalet steg i simplex-metoden, som uppfanns 1947 av amerikansk matematiker George Dantzig, växer exponentiellt med inmatningens storlek. Men 1979 upptäckte rysk matematiker Leonid Khachian en polynom tidsalgoritm-dvs, antalet beräkningssteg växer som en kraft av antalet variabler, snarare än exponentiellt—vilket visar att linjära programmeringsproblem faktiskt är P. Denna upptäckt möjliggjorde lösningen av tidigare svårbara problem.

ett problem är NP-svårt om en algoritm för dess lösning kan ändras för att lösa något NP-problem—eller något P-problem, för den delen, eftersom P-problem är en delmängd av NP-problem. (Inte alla NP-hårda problem är dock medlemmar i klassen av NP-problem.) Ett problem som är både NP och NP-hard sägs vara NP-complete., Att hitta en effektiv algoritm för alla NP-kompletta problem innebär således att en effektiv algoritm kan hittas för alla NP-problem, eftersom en lösning för alla problem som hör till denna klass kan omarbetas till en lösning för någon annan medlem i klassen., I 1971 amerikanska datavetare Stephen Cook visade att satisfiability problem (ett problem att tilldela värden till variabler i en formel i Boolesk algebra så att uttalandet är sant) är NP-komplett, vilket var det första problemet visat sig vara NP-komplett och öppnade vägen för att visa andra problem som är medlemmar i klassen av NP-kompletta problem. Ett känt exempel på ett NP-komplett problem är resande säljare problemet, som har breda tillämpningar i optimering av transport scheman., Det är inte känt om några polynom tidsalgoritmer någonsin kommer att hittas för NP-kompletta problem, och att bestämma om dessa problem är tractable eller intractable är fortfarande en av de viktigaste frågorna i teoretisk datavetenskap. En sådan upptäckt skulle bevisa att P = NP = NP-komplett och revolutionera många fält inom datavetenskap och matematik.

till exempel bygger modern kryptografi på antagandet att factoring av produkten av två stora primtal inte är P., Observera att det är lätt att verifiera produkten av två primtal (polynomtid), men det är svårt att beräkna de två främsta faktorerna. Upptäckten av en effektiv algoritm för factoring stort antal skulle bryta de flesta moderna krypteringssystem.

år 2000 utarbetade amerikansk matematiker Stephen Smale en inflytelserik lista över 18 viktiga matematiska problem för att lösa i det 21: a århundradet. Det tredje problemet på hans lista var P mot NP problem., År 2000 var det särskilt ett Millennium Problem, en av sju matematiska problem som valts ut av Clay Mathematics Institute i Cambridge, Massachusetts, USA, för en särskild utmärkelse. Lösningen för varje Millennieproblem är värt $ 1 miljoner.