P versus NP is de volgende vraag die van belang is voor mensen die met computers en in de wiskunde werken: Kan elk opgelost probleem waarvan het antwoord snel door een computer kan worden gecontroleerd ook snel door een computer worden opgelost? P en NP zijn de twee soorten rekenproblemen waarnaar verwezen wordt: P-problemen zijn voor computers snel op te lossen en worden dus als "gemakkelijk" beschouwd. NP-problemen zijn problemen waarvan een voorgesteld antwoord snel (in polynoomtijd) door een computer gecontroleerd kan worden, maar die niet per se snel op te lossen zijn.

Wat betekenen P en NP precies?

In formele termen is P de verzameling van beslissingsproblemen (ja/nee-vragen) die een deterministische Turingmachine in polynomiale tijd kan oplossen. Met andere woorden: er bestaat een algoritme waarvan de uitvoeringstijd een polynoom is in de grootte van de invoer (bijvoorbeeld O(n), O(n^2), O(n^3), enz.). Voorbeelden van problemen in P zijn het vinden van de kortste route in een graaf met gewichten (Dijkstra), sorteren en het bepalen of een getal deelbaar is door een ander getal.

NP is de verzameling beslissingsproblemen waarvoor, als het juiste antwoord "ja" is, er een bewijs (ook wel 'certificate') bestaat dat in polynomiale tijd door een deterministische machine geverifieerd kan worden. Equivalent: NP is de klasse van problemen die een niet-deterministische Turingmachine in polynomiale tijd kan oplossen. Belangrijke voorbeelden van NP-problemen zijn de booleaanse satisfiability (SAT), het beslissingsprobleem van de handelsreiziger (is er een route van lengte ≤ K?) en subset-sum.

NP-compleet en NP-hard

Niet alle NP-problemen zijn even moeilijk. Een probleem heet NP-compleet als het twee eigenschappen heeft:

  • Het behoort tot NP.
  • Elk probleem in NP kan in polynomiale tijd worden gereduceerd tot dit probleem (het is dus minstens zo moeilijk als elk ander probleem in NP).

Een probleem dat minstens zo moeilijk is als de moeilijkste problemen in NP, maar zelf niet in NP hoeft te liggen, wordt NP-hard genoemd.

De eerste belangrijke stap in het formeel vastleggen van NP-compleetheid is de zogenaamde Cook–Levin-stelling, die aantoont dat het booleaanse satisfiability-probleem (SAT) NP-compleet is. Stephen Cook introduceerde in 1971 de veelgebruikte formulering van het P versus NP-vraagstuk in zijn artikel "The complexity of theorem proving procedures". Kort daarna maakte Richard Karp (1972) een lijst van tientallen natuurlijke problemen waarvan werd aangetoond dat ze NP-compleet zijn, wat de relevantie van het begrip vergrootte.

Korte geschiedenis

De vraag heeft oudere wortels: in 1956 schreef Kurt Gödel een brief aan John von Neumann waarin hij vroeg of een bepaald NP-volledig probleem in kwadratische of lineaire tijd opgelost kon worden. De moderne, precieze formulering van P versus NP dateert echter uit het begin van de jaren zeventig met werk van Cook en Levin.

Waarom is het belangrijk?

Het P versus NP-probleem is fundamenteel omdat het bepaalt of veel ogenschijnlijk moeilijke problemen in de praktijk efficiënt kunnen worden opgelost. Dit heeft directe gevolgen voor:

  • Cryptografie: Veel huidige cryptografische systemen (zoals RSA) hangen ervan af dat bepaalde problemen (bijv. factorisatie, discrete log) in de praktijk niet snel oplosbaar zijn. Als P=NP en er bestaan praktische polynomiale algoritmen, dan zouden veel encryptiesystemen onveilig worden.
  • Optimalisatie en planning: Tal van problemen in logistiek, productie, en kunstmatige intelligentie zijn NP-compleet. Als P=NP zou dit de deur openen naar efficiënte exacte oplossingen voor veel optimalisatievragen; als P≠NP betekent dat dat heuristieken en benaderingsalgoritmen de beste praktische benadering blijven.
  • Wiskunde en bewijscontrole: Als P=NP zouden wiskundige bewijzen mogelijk automatisch en efficiënt gevonden kunnen worden, wat grote impact heeft op de manier waarop nieuwe stellingen ontdekt worden.

Gevolgen van beide mogelijkheden

  • Als P = NP: elk probleem waarvan een oplossing snel geverifieerd kan worden, kan ook snel worden opgelost. Dat zou vele huidige cryptosystemen bedreigen en veel AI- en optimalisatieproblemen fundamenteel veranderen. In de praktijk moet er ook gekeken worden naar de orde van het polynoom en constante factoren; een theoretisch polynomiaal algoritme van hoge graad kan nog steeds onbruikbaar zijn.
  • Als P ≠ NP: dan bestaat er een intrinsieke scheiding tussen problemen die snel te verifiëren maar niet snel op te lossen zijn. Dat bevestigt de moeilijkheid van vele combinatorische problemen en ondersteunt de veiligheid van cryptografische aannames (hoewel sommige specifieke problemen nog steeds tractabel kunnen blijken).

Huidige status en beloning

Tegenwoordig wordt het P versus NP-probleem door velen beschouwd als het belangrijkste open probleem in de theoretische informatica. Het is één van de zeven Millennium Prize Problems die door het Clay Mathematics Institute zijn geselecteerd; aan de eerste juiste oplossing is een prijs van 1.000.000 dollar verbonden. Tot op heden is er geen algemeen geaccepteerd bewijs geleverd dat P=NP of dat P≠NP; de meeste deskundigen vermoeden dat P≠NP, maar dat blijft ongerezen.

Hoe benaderen onderzoekers het probleem?

Onderzoekers gebruiken technieken als redukties tussen problemen, complexiteitslower-bounds, bewijscomplexiteit, en verbindingen met andere takken van wiskunde en informatica (zoals cryptografie, circuitcomplexiteit en randomized algorithms). Hoewel er vele deelsuccesjes en interessante resultaten zijn — bijvoorbeeld over speciale gevallen, restricties of resultaten in relatieve modellen — is het algemene probleem nog steeds open.

Voorbeelden van bekende problemen

  • In P: kortste pad (Dijkstra), matrixvermenigvuldiging (voor sommige algoritmen), grote-rekenkunde-bepalingen zoals euclidische algoritmen.
  • NP (en vaak NP-compleet): SAT (booleaanse satisfiability), clique-probleem, vertex cover, Hamiltoniaanse cyclus, subset-sum en het beslissingsprobleem voor de handelsreiziger.

Samengevat: P versus NP is een kernvraag over de grenzen van efficiënt rekenen. De uitkomst heeft diepgaande theoretische en praktische implicaties, en het blijft een van de meest intrigerende open problemen in de informatica en de wiskunde.