Polynomiale tijd
Polynomiale tijd is een term uit de informatica die aangeeft hoe snel de rekentijd van een algoritme oploopt naarmate de invoer groter wordt. Simpel gezegd: als je de invoer twee keer zo groot maakt, wordt het probleem dan een beetje moeilijker, of ontploffen de rekenkosten? Bij polynomiale tijd blijft de groei beheersbaar, ook al kost het meer werk. Het is het verschil tussen een telefoonboek doorzoeken op achternaam, waarbij je met iedere extra pagina maar een beetje langer zoekt, en het proberen van alle mogelijke combinaties van een viercijferig cijferslot, waarbij elk extra cijfer het aantal pogingen met een factor tien laat groeien.
Dat onderscheid lijkt abstract, maar het bepaalt in de praktijk of een probleem door een computer in seconden, uren, of nooit binnen een mensenleven kan worden opgelost. Algoritmes die in polynomiale tijd werken, gelden in de informatica als praktisch haalbaar, ook als ze soms nog behoorlijk traag zijn. Algoritmes waarvan de rekentijd exponentieel groeit, worden al bij relatief kleine invoergroottes onwerkbaar traag, zelfs op de snelste supercomputers. Dit onderscheid tussen "haalbaar" en "onhaalbaar" rekenwerk vormt de kern van de complexiteitstheorie, een tak van de informatica en wiskunde die onderzoekt hoeveel rekenkracht problemen fundamenteel vereisen.
Wat is het precies?
Om de snelheid van een algoritme te beschrijven, kijken informatici naar het aantal rekenstappen dat het nodig heeft, uitgedrukt als functie van de grootte van de invoer. Die grootte noemen ze meestal n: bijvoorbeeld het aantal getallen in een lijst, of het aantal steden in een routeplanningsprobleem. Om te vermijden dat je moet uitrekenen wat er op elke specifieke computer gebeurt, gebruiken onderzoekers de zogeheten Big O-notatie. Die geeft alleen de groeivorm weer, niet de exacte tijd in seconden: een algoritme met tijd O(n) wordt dubbel zo traag als je de invoer verdubbelt, een algoritme met tijd O(n²) wordt vier keer zo traag.
Polynomiale groei betekent dat de rekentijd toeneemt volgens een formule als n, n², n³ of een hogere macht van n, maar niet sneller dan dat. Exponentiële groei, zoals 2 tot de macht n, is fundamenteel anders: bij elke extra eenheid aan invoer verdubbelt de rekentijd opnieuw. Bij n = 10 is 2^n nog maar 1024, maar bij n = 100 is 2^n al een getal met meer dan dertig cijfers, groter dan het aantal atomen dat een computer ooit zou kunnen doorrekenen. Polynomiale algoritmes blijven daarentegen bij grotere invoer relatief beheersbaar in groei.
Op basis van dit onderscheid definieerden informatici de complexiteitsklasse P: de verzameling van alle problemen die een computer kan oplossen in polynomiale tijd. Daarnaast bestaat de klasse NP: problemen waarvan een gegeven oplossing snel, dat wil zeggen in polynomiale tijd, te controleren is, ook al is het niet bekend of de oplossing zelf ook snel te vinden is. Elk P-probleem zit automatisch ook in NP, want als je iets snel kunt oplossen, kun je de uitkomst ook snel controleren. Sommige NP-problemen zijn zo lastig dat elk ander NP-probleem ernaar te herleiden is; die problemen heten NP-compleet. Als er ooit een polynomiaal algoritme wordt gevonden voor slechts één NP-compleet probleem, zou dat betekenen dat P en NP eigenlijk hetzelfde zijn.
Wat wil men ermee bereiken?
Het doel van dit onderzoek is niet alleen theoretisch. Weten of een probleem in polynomiale tijd oplosbaar is, bepaalt of ingenieurs er praktisch mee aan de slag kunnen, of dat ze noodgedwongen op zoek moeten naar benaderingen, slimme trucs, of gewoon moeten accepteren dat een exacte oplossing buiten bereik ligt. Dit raakt direct aan technologie die mensen dagelijks gebruiken.
Een belangrijk praktisch voorbeeld is cryptografie. Het veelgebruikte RSA-versleutelingssysteem, dat onder meer beveiligde webverbindingen mogelijk maakt, steunt erop dat het factoriseren van een heel groot getal in zijn priemfactoren op een gewone computer niet in polynomiale tijd kan. Zolang niemand een snelle klassieke methode vindt om grote getallen te factoriseren, blijft het praktisch onmogelijk om de versleuteling te kraken door alle mogelijkheden te proberen. Dat maakt de vraag naar polynomiale oplosbaarheid direct relevant voor internetveiligheid.
Ook buiten cryptografie is het onderscheid belangrijk. Routeplanning voor pakketbezorgers, roosterplanning in ziekenhuizen, chipontwerp en logistieke optimalisatie bij luchtvaartmaatschappijen bevatten vaak problemen die in het slechtste geval extreem traag zijn om exact op te lossen. Onderzoekers proberen dan ofwel te bewijzen dat er toch een polynomiaal algoritme bestaat, ofwel praktische benaderingsmethodes te ontwikkelen die een goede, maar niet per se perfecte oplossing snel genoeg vinden.
Voorbeelden uit de praktijk
Een van de bekendste doorbraken is de AKS-priemtest, gepubliceerd in 2002 door de Indiase onderzoekers Manindra Agrawal, Neeraj Kayal en Nitin Saxena. Zij bewezen dat je van een willekeurig getal in polynomiale tijd kunt vaststellen of het een priemgetal is, zonder afhankelijk te zijn van onbewezen wiskundige aannames. Dit was decennialang een open vraag en gold als een mijlpaal in de complexiteitstheorie.
Een ander voorbeeld is het ellipsoïde-algoritme van de Sovjet-wiskundige Leonid Khachiyan uit 1979. Hij toonde aan dat lineair programmeren, een wiskundige techniek die veel wordt gebruikt bij optimalisatievraagstukken in productie, transport en economie, in polynomiale tijd oplosbaar is. Dit resultaat had grote invloed op de operationele planning binnen bedrijven en overheden, ook al bleek de in de praktijk gebruikte simplex-methode vaak sneller te werken dan het theoretisch elegantere ellipsoïde-algoritme.
In 1994 liet de Amerikaanse wiskundige Peter Shor zien dat het factoriseren van grote getallen wél in polynomiale tijd kan, mits je beschikt over een quantumcomputer. Zijn algoritme van Shor maakt gebruik van quantummechanische effecten om de zwakke plek van RSA-cryptografie in theorie te kunnen aanvallen. Op dit moment bestaan er nog geen quantumcomputers die krachtig en foutbestendig genoeg zijn om Shors algoritme op de grote getallen te draaien die in echte encryptie worden gebruikt, maar het vooruitzicht heeft wel geleid tot serieuze voorbereidingen in de beveiligingswereld.
Ten slotte is er het klassieke handelsreizigersprobleem (traveling salesman problem): gegeven een lijst steden en de afstanden ertussen, wat is de kortste route die elke stad precies één keer bezoekt en terugkeert naar het startpunt? Dit probleem is NP-moeilijk, wat betekent dat er geen bekend polynomiaal algoritme is dat gegarandeerd de optimale route vindt voor elke mogelijke invoer. In de praktijk gebruiken logistieke bedrijven en navigatiesystemen slimme benaderingsalgoritmes die niet altijd de perfecte route vinden, maar wel binnen aanvaardbare tijd een route die dicht bij het optimum ligt.
Hoe ver is de techniek?
De centrale open vraag in dit vakgebied is of P gelijk is aan NP, kortweg het "P versus NP"-probleem. De formele basis hiervoor werd gelegd door de Amerikaanse informaticus Stephen Cook en, onafhankelijk van hem, de Sovjet-wiskundige Leonid Levin, die in 1971 het zogeheten Cook-Levin theorema publiceerden. Zij bewezen het bestaan van NP-complete problemen. In 1972 breidde Richard Karp dit uit door aan te tonen dat eenentwintig bekende problemen, waaronder varianten van planningsproblemen, NP-compleet zijn.
Sindsdien, meer dan vijftig jaar later, is er geen bewijs gevonden dat P wel of niet gelijk is aan NP. De meerderheid van de onderzoekers vermoedt dat P ongelijk is aan NP, dat wil zeggen dat er problemen bestaan waarvan de oplossing wel snel te controleren, maar niet snel te vinden is. Dit vermoeden is echter niet bewezen, en het Clay Mathematics Institute looft sinds 2000 een miljoen dollar uit voor wie het probleem definitief oplost, als een van de zeven zogeheten Millennium Prize Problems. Tot nu toe is alleen het vermoeden van Poincaré uit die lijst daadwerkelijk bewezen, in 2003 door de Russische wiskundige Grigori Perelman.
De opkomst van quantumcomputers heeft het onderwerp een nieuwe praktische urgentie gegeven, zonder de kernvraag zelf op te lossen. Shors algoritme laat zien dat quantumcomputers bepaalde problemen sneller kunnen aanpakken dan klassieke computers, maar voor zover nu bekend is lossen quantumcomputers de meeste NP-complete problemen niet in polynomiale tijd op. Wel heeft het vooruitzicht van bruikbare quantumcomputers geleid tot de ontwikkeling van zogeheten post-quantum cryptografie: nieuwe versleutelingsmethodes die naar verwachting ook bestand zijn tegen aanvallen met quantumalgoritmes. Dit blijft een actief en nog volop in ontwikkeling zijnd onderzoeksveld, met aanzienlijke onzekerheid over de tijdshorizon waarop krachtige quantumcomputers daadwerkelijk een praktische dreiging vormen.
Wie werken eraan?
Het Clay Mathematics Institute, een Amerikaanse non-profitorganisatie voor wiskundig onderzoek, houdt de Millennium Prize voor het P versus NP-probleem in stand en documenteert de formele probleemstelling. Academische centra als het Massachusetts Institute of Technology (MIT), Princeton University, Stanford University en de University of California, Berkeley, behoren tot de belangrijkste plekken waar complexiteitstheorie wordt onderzocht en onderwezen.
Historisch gezien zijn de sleutelfiguren onder anderen Stephen Cook, Leonid Levin en Richard Karp, wier werk in de jaren zeventig de basis legde voor het vakgebied, en Peter Shor, wiens quantumalgoritme uit 1994 de relatie tussen complexiteitstheorie en quantummechanica op de kaart zette. Manindra Agrawal, Neeraj Kayal en Nitin Saxena, verbonden aan het Indian Institute of Technology Kanpur, leverden met de AKS-priemtest in 2002 een van de recentere invloedrijke resultaten.
Op de meer toegepaste kant werken bedrijven als IBM Quantum en Google Quantum AI aan de ontwikkeling van quantumcomputers die ooit algoritmes als dat van Shor op relevante schaal zouden kunnen uitvoeren. Het Amerikaanse standaardisatie-instituut NIST (National Institute of Standards and Technology) coördineert internationaal de ontwikkeling en standaardisatie van post-quantum cryptografische algoritmes, als voorbereiding op een toekomst waarin bestaande versleuteling mogelijk kwetsbaar wordt.