P versus NP probleem, in volledige polynoom versus niet-deterministisch polynoom probleem, in computationele complexiteit (een subveld van theoretische informatica en wiskunde), de vraag of alle zogenaamde NP problemen eigenlijk P problemen zijn. Een P-probleem is een probleem dat kan worden opgelost in “polynomiale tijd”, wat betekent dat een algoritme bestaat voor zijn oplossing zodanig dat het aantal stappen in het algoritme wordt begrensd door een polynomiale functie van n, waarbij n overeenkomt met de lengte van de invoer voor het probleem., Dus, P problemen worden gezegd dat gemakkelijk, of tractable. Een probleem wordt NP genoemd als de oplossing ervan kan worden geraden en geverifieerd in polynomiale tijd, en niet-deterministisch betekent dat er geen specifieke regel wordt gevolgd om de gok te maken.Lineaire programmeerproblemen zijn NP, omdat het aantal stappen in de simplex-methode, uitgevonden in 1947 door de Amerikaanse wiskundige George Dantzig, exponentieel groeit met de grootte van de input. In 1979 ontdekte de Russische wiskundige Leonid Khachian echter een polynomiaal tijdalgoritme-d.w.z.,, het aantal computationele stappen groeit als een macht van het aantal variabelen, in plaats van exponentieel—waardoor blijkt dat lineaire programmeerproblemen zijn eigenlijk P. Deze ontdekking liet de oplossing van voorheen hardnekkige problemen.

een probleem is NP-hard als een algoritme voor zijn oplossing kan worden aangepast om een NP—probleem op te lossen-of een P-probleem, wat dat betreft, omdat P-problemen een subset zijn van NP-problemen. (Niet alle NP-harde problemen behoren echter tot de klasse van NP-problemen.) Een probleem dat zowel NP als NP-hard is wordt gezegd NP-compleet te zijn., Dus, het vinden van een efficiënt algoritme voor elk NP-compleet probleem impliceert dat een efficiënt algoritme kan worden gevonden voor alle NP problemen, omdat een oplossing voor elk probleem dat tot deze klasse kan worden herschikt in een oplossing voor elk ander lid van de klasse., In 1971 bewees de Amerikaanse computerwetenschapper Stephen Cook dat het probleem van de bevrediging (een probleem van het toewijzen van waarden aan variabelen in een formule in de Booleaanse algebra, zodat de stelling waar is) NP-compleet is, wat het eerste probleem was dat NP-compleet bleek te zijn en de weg opende naar het tonen van andere problemen die behoren tot de klasse van NP-complete problemen. Een beroemd voorbeeld van een NP-compleet probleem is het reizende verkoper probleem, dat brede toepassingen in de optimalisatie van transportschema ‘ s heeft., Het is niet bekend of er ooit polynomiale tijdalgoritmen zullen worden gevonden voor NP-complete problemen, en het bepalen of deze problemen tracteerbaar of hardnekkig zijn blijft een van de belangrijkste vragen in de theoretische informatica. Een dergelijke ontdekking zou bewijzen dat P = NP = NP-vele gebieden in de informatica en wiskunde compleet en revolutionair maakt.

moderne cryptografie berust bijvoorbeeld op de veronderstelling dat het product van twee grote priemgetallen niet P is., Merk op dat het controleren van het product van twee priemgetallen eenvoudig is (polynomiale tijd), maar het berekenen van de twee priemfactoren is moeilijk. De ontdekking van een efficiënt algoritme voor het factoreren van grote getallen zou de meeste moderne encryptie-schema ‘ s breken.

in 2000 bedacht De Amerikaanse wiskundige Stephen Smale een invloedrijke lijst van 18 belangrijke wiskundige problemen voor het oplossen van problemen in de 21e eeuw. Het derde probleem op zijn lijst was het P versus NP probleem., In 2000 werd het een Millennium probleem, een van de zeven wiskundige problemen geselecteerd door het Clay Mathematics Institute van Cambridge, Massachusetts, Verenigde Staten, voor een speciale prijs. De oplossing voor elk millenniumprobleem is 1 miljoen dollar waard.