P vs. NP

Op zoek naar het ideale lief? Of kan je niet meer zo lang wachten op die pakjes van Zalando? Je bent niet alleen. Iedereen is ooit wel eens op zoek gegaan naar de beste oplossing voor een probleem. Vaak denken we erover na of vragen we advies, maar wat als we het nu eens wiskundig zouden aanpakken? Een heuse tak van de wetenschap houdt zich bezig met de vraag: hoe vinden we de optimale oplossing?

het wiskundige kluwen ontrafeld: volg de rode draad 

P vs. NP kan het antwoord bieden op al je problemen. Het vraagstuk is een van de grootste onopgeloste problemen in de computerwetenschappen, zo groot zelfs dat het Clay Mathematics Institute een miljoen dollar uitreikt aan de persoon die dit probleem kan oplossen. Het is een van de zeven Milleniumproblemen. Op het eerste gezicht is het probleem maar enkele letters, maar die kunnen grote gevolgen hebben voor ons dagelijks leven. 

P vs. NP is een probleem uit de computationele complexiteitstheorie. Klinkt verschrikkelijk, maar eigenlijk probeert die tak van de wiskunde gewoon problemen die door een computer kunnen worden opgelost, in te delen op basis van hun moeilijkheidsgraad. P en NP zijn een paar van de mogelijke categorieën. Naast overzicht creëren geeft deze indeling aan waar de praktische limieten van computers liggen. Een computer volgt namelijk een wiskundig stappenplan dat een algoritme wordt genoemd. Nu, die algoritmes kunnen al snel heel ingewikkeld worden.  Dat brengt ons bij P vs. NP. Hopelijk zijn jullie klaar voor een paar fancy definities – Wikipedia schiet te hulp.

De definitie voor P luidt: “In de complexiteitstheorie is P een complexiteitsklasse die alle beslissingsproblemen bevat die in polynomiale tijd opgelost kunnen worden door een deterministische turingmachine.” 

NP is dan weer als volgt: “NP, de aanduiding voor niet-deterministisch polynomiaal, is een complexiteitsklasse die alle beslissingsproblemen bevat die oplosbaar zijn in polynomiale tijd door een niet-deterministische turingmachine.”  

Pijnlijke definities, gelukkig niet te kennen voor het examen. Toch vallen ze mee. P bevat relatief gemakkelijke problemen waarvoor een oplossingsalgoritme gekend is. NP daarentegen bevat relatief moeilijke problemen waarvoor geen stappenplan gekend is, maar als er een oplossing is, kan die gemakkelijk en relatief snel gecontroleerd worden. Denk aan het vinden van een lief, duidelijk een NP-probleem. Jouw ideaal lief vinden is een hele opgave, maar eens je een lief hebt is het niet zo moeilijk om te checken of ze de sleutel tot jouw hart (en andere delen) zijn. Het grote verschil tussen P en NP is dat bij P het stappenplan eenduidig is, terwijl bij NP je meerdere evenwaardige keuzes hebt bij sommige stappen. In wiskundige taal wordt dat eenduidig zijn van een stappenplan een deterministische turingmachine genoemd.  

Na vele kronkels in ons pad zijn wij nu eindelijk bij ons doel: de definitie van het probleem. P vs. NP vraagt zich af of de moeilijke NP -problemen kunnen opgesplitst worden in gemakkelijkere P-problemen. Lijkt simpel, maar een bewijs is nog ver zoek. Al sinds 1971 speelt deze vraag een prominente rol in de computerwetenschappen. Als iemand kan bewijzen dat P gelijk is aan NP of juist niet, zou dat grote gevolgen hebben.  

algoritme voor het optimale lief: de wiskundige utopie 

Stel dat P gelijk is aan NP. Wat betekent dat voor jou? Wel, jouw oneindige zoektocht naar een ideaal lief zal gestroomlijnd worden. Passeer even langs de wiskundige bij jou om de hoek om je algoritme op te halen. Het stappenplan voor het ideale lief ligt nu in je handen. Geen goktoestanden, geen twijfels, je ideale partner ligt binnen handbereik. In theorie dan.  

Als er bewezen wordt dat P niet gelijk is aan NP, heeft dat zeker ook zijn nut. Nu je weet dat een stappenplan voor je ideale lief niet op te stellen is, kan je je beroepen op de traditionele methode. We gaan op zoek naar een oplossing die ‘goed genoeg’ is (maar zeg dat best niet tegen je lief). Een eerste strategie: neem simpelweg een voldoende grote steekproef op de TD’s in betere tijden (testcriteria zelf op te stellen). Mocht iemand u hierop aanspreken gebruik de volgende verantwoording: "de wetenschap weet het zelf ook niet beter!" Voor hen onder ons die de bovenstaande tijdsinvestering niet wensen te maken, is er een alternatieve strategie: beroep je op de heuristiek. Stel een stappenplan op dat bij je past en hoop zo een partner te vinden die ‘goed genoeg’ is. De exacte inhoud van zulk algoritme is zelf te bepalen. Deel zoals ik IQ-testen uit of vraag naar hun mening over analytische versus continentale filosofie, mocht je wat filosofischer aangelegd zijn. Als je wat sneller vooruit wil gaan, kan je gewoonweg enkel blondjes of psychologen in spe daten. Jouw voorkeuren liggen bij jou. 

het wiskundige kluwen ontrafeld: de consequenties 

Het vinden van een lief is een ernstige zaak. Maar wat met de praktische consequenties voor de maatschappij? Indien er bewezen kan worden dat P gelijk is aan NP, is geen enkele computer meer veilig. Ingewikkelde inscripties kunnen gewoon herleid worden tot simpel op te lossen problemen. Belangrijk om te vermelden: oplosbaar betekent niet altijd realistisch haalbaar. De simpele P-problemen kunnen een erg lange oplostijd hebben. Denk aan jaren, decennia, zelfs millennia. De echte gevolgen zijn dus nog te bezien. Wat we wel weten, is dat een gigantische hoeveelheid aan problemen die nu te complex zijn om op te lossen, plots wel oplosbaar worden. De gevolgen voor de computerwetenschappen, misschien zelfs de wereld, zullen gelijk zijn aan een nieuwe industriële revolutie. En dat pakketje van Zalando zal nu, in theorie, écht zo snel mogelijk bij jou aankomen. 

Stel nu dat er bewezen wordt dat P niet gelijk is aan NP. Dan zijn we zeker dat onkraakbare computers bestaan, want nu weten we dat eigenlijk echt niet. Al een geruststelling, want dan kan jouw ‘bijna’ optimale lief met zekerheid niet de grootte van jouw steekproef achterhalen. Voor de wiskundigen zijn de implicaties duidelijk: het NP-probleem is waarschijnlijk niet computationeel op te lossen dus we beginnen er ook niet aan. Zo kunnen ze hun tijd en energie steken in algoritmen die een oplossing zoekt die 'goed genoeg' is. En goed genoeg is regelmatig echt goed. Voor ons probleem met de pakketjes van Zalando komen die oplossingen tot 99%-99,5% in de buurt van de allerbeste oplossing.  

Dus mocht jij je eens vervelen op een koude zondagavond, stort je op dit probleem. Een miljoen dollar of jouw perfecte lief, een betere motivatie zou ik niet kunnen vinden. Maar ach, een Zalando-pakketje dat snel aankomt, is voor mij al motivatie genoeg.