P versus NP problem, i full polynom versus nondeterministic polynom problem, i beregningsorientert kompleksitet (en subfield av teoretisk informatikk og matematikk), spørsmålet om alle såkalte NP-problemer er faktisk P problemer. En P-problemet er en som kan løses i «polynomisk tid,» som betyr at en algoritme eksisterer for sin løsning slik at antall trinnene i algoritmen er avgrenset av en polynomisk funksjon av n, der n tilsvarer lengden av input for problemet., Dermed, S problemer er sagt å være lett, eller føyelig. Et problem er kalt NP om sin løsning kan være å gjette, og bekreftet i polynomisk tid, og nondeterministic betyr at ingen bestemt regel er fulgt for å gjøre det enkelt.

Lineær programmering problemer er NP, som antall trinn i simplex-metoden, oppfunnet i 1947 av Amerikanske matematikeren George Dantzig, vokser eksponentielt med størrelsen på input. Men i 1979 russiske matematiker Leonid Khachian oppdaget en polynomisk tid-algoritme—dvs., antall computational trinn vokser som en effekt av antall variabler, snarere enn eksponentielt—og dermed vise at lineær programmering problemer er faktisk S. Dette funnet tillatt løsning av tidligere uløselige problemer.

Et problem er NP-hard hvis en algoritme for sin løsning kan være endret for å løse eventuelle NP-problem—eller noen P problemet, for den saks skyld, som P problemer er en delmengde av NP-problemer. (Ikke alle NP-hard problemer er medlemmer av klassen av NP-problemer, men.) Et problem som er både NP og NP-hard sies å være NP-komplett., Derfor, å finne en effektiv algoritme for alle NP-komplett problem innebærer at en effektiv algoritme kan bli funnet for alle NP-problemer, siden en løsning for ethvert problem som hører til denne klassen kan bli støpt inn i en løsning for andre medlemmer av klassen., I 1971 Amerikansk forsker Stephen Cook viste seg at satisfiability problem (et problem for tilordning av verdier til variabler i en formel i Boolsk algebra slik at utsagnet er sant), er NP-komplett, som var det første problemet har vist seg å være NP-komplett og åpnet veien for å vise andre problemer som er medlemmer av klassen av NP-komplette problemer. Et berømt eksempel på et NP-komplett problem er traveling salesman problem, som har bred programmer i optimalisering av transport tidsplaner., Det er ikke kjent om noen polynomisk tid-algoritmer noensinne vil bli funnet for NP-komplette problemer, og å avgjøre om disse problemene er føyelig eller problematiske er fortsatt en av de viktigste spørsmål i teoretisk informatikk. Et slikt funn ville bevise at P = NP = NP-komplett og revolusjonere mange felt i informatikk og matematikk.

For eksempel, moderne kryptografi baserer seg på antagelsen om at factoring produktet av to store primtall er ikke S., Vær oppmerksom på at kontrollere produkt av to primtall er lett (polynomisk tid), men computing de to prime faktorer som er vanskelig. Oppdagelsen av en effektiv algoritme for factoring stort antall ville bryte mest moderne kryptering ordninger.

I 2000 Amerikanske matematikeren Stephen Smale utarbeidet en liste over innflytelsesrike 18 viktig for å løse matematiske problemer i det 21. århundre. Det tredje problemet på sin liste ble det versus S NP-problem., Også i 2000 ble det utpekt en Millennium Problem, en av sju matematiske problemer som er valgt ut av Clay Mathematics Institute i Cambridge, Massachusetts, USA, for en spesiell pris. Løsningen for hver Millennium Problemet er verdt $1 million.