P versus NP problem, i fuld polynomium versus nondeterministic polynomial problem, i den beregningsmæssige kompleksitet (et underfelt af teoretisk datalogi og matematik), spørgsmålet om, hvorvidt alle såkaldt NP-problemer er faktisk S problemer. En P er et problem, der kan løses i “polynomiel tid,” hvilket betyder, at en algoritme, der eksisterer for sin løsning, sådan at antallet af trin i algoritmen er afgrænset af en polynomial funktion af n, hvor n svarer til længden af input til problemet., Dermed, p problemer siges at være let, eller medtagelig. Et problem kaldes NP, hvis dets løsning kan gættes og verificeres i polynomisk tid, og nondeterministisk betyder, at ingen særlig regel følges for at gætte.lineære programmeringsproblemer er NP, da antallet af trin i simple. – metoden, opfundet i 1947 af den amerikanske matematiker George dant .ig, vokser eksponentielt med størrelsen på input. I 1979 opdagede den russiske matematiker Leonid Khachian imidlertid en polynomial tidsalgoritme-dvs—,, antallet af beregningstrin vokser som en effekt af antallet af variabler, snarere end eksponentielt—hvilket viser, at lineære programmeringsproblemer faktisk er P. denne opdagelse muliggjorde løsning af tidligere uhåndterlige problemer.

et problem er NP-hard, hvis en algoritme til dens løsning kan ændres til at løse ethvert NP—problem-eller ethvert p-problem, for den sags skyld, da P-problemer er en delmængde af NP-problemer. (Ikke alle NP-hard problemer er medlemmer af klassen af NP problemer, dog.) Et problem, der er både NP og NP-hard siges at være NP-komplet., Således finde en effektiv algoritme for enhver NP-komplet problem indebærer, at en effektiv algoritme kan findes for alle NP problemer, da en løsning til ethvert problem, der tilhører denne klasse, kan omarbejdes til en løsning for ethvert andet medlem af klassen., I 1971 Amerikansk matematiker Stephen Cook viste sig, at satisfiability problem (et problem for tildeling af værdier til variablerne i formlen i Boolsk algebra sådan, at udsagnet er sandt) er NP-komplet, som var det første problem viste sig at være NP-komplet, og åbnede den måde at vise andre problemer, der er medlemmer af klassen af NP-komplette problemer. Et berømt eksempel på et NP-komplet problem er traveling salesman problem, som har brede anvendelser i optimering af transportplaner., Det vides ikke, om nogen polynomiel tid algoritmer nogensinde vil blive fundet for NP-komplette problemer, og afgøre, om disse problemer er føjelig eller genstridig er fortsat et af de vigtigste spørgsmål i teoretisk datalogi. En sådan opdagelse ville bevise, at P = NP = NP-komplet og revolutionere mange felter inden for datalogi og matematik.for eksempel er moderne kryptografi afhængig af antagelsen om, at factoring af produktet af to store primtal ikke er P., Bemærk, at det er let at verificere produktet af to primtal (polynomisk tid), men at beregne de to primære faktorer er svært. Opdagelsen af en effektiv algoritme til factoring store tal ville bryde de fleste moderne kryptering ordninger.

i 2000 udtænkte den amerikanske matematiker Stephen Smale en indflydelsesrig liste over 18 vigtige matematiske problemer til løsning i det 21.århundrede. Det tredje problem på hans liste VAR P versus NP problem., Også i 2000 blev det udpeget et årtusinde Problem, en af syv matematiske problemer udvalgt af Clay Mathematics Institute of Cambridge, Massachusetts, USA, for en særlig pris. Løsningen for hvert årtusinde Problem er værd $ 1 million.