Stel je een schaakbord voor. Plaats twee rivaliserende koninginnen erop, zodat ze elkaar niet direct kunnen aanvallen. Makkelijk? Nou, herhaal het proces nu met zes extra koninginnen. Gecompliceerd, maar mogelijk. Tot slot breid je het probleem uit naar borden van willekeurige grootte, met een willekeurig aantal vooraf ingestelde koninginnen erop. Het zogenaamde "probleem van de 1000 koninginnen" is niets meer dan een op zichzelf staand voorbeeld om een veel complexere oefening uit te leggen, "P versus NP" tot het punt dat het Clay Mathematics Institute een miljoen dollar biedt voor het eerste positieve bewijs.
De Zeven Millenniumproblemen
Er bestaat een zeer interessante competitie die "De Zeven Millenniumproblemen" wordt genoemd. In het jaar 2000 gestart door het Clay Mathematics Institute, is het doel om antwoorden te vinden op zeven klassieke problemen die zich in de loop der jaren tegen een oplossing hebben "verzet". Tot nu toe is het enige probleem dat een passend bewijs heeft gekregen het "vermoeden van Poincaré" ontwikkeld door de Russische wiskundige Grigori Perelman.
Het instituut aarzelde niet om hem een miljoen dollar aan te bieden voor zijn werk, maar Perelman weigerde, zeggend dat zijn bijdrage niet groter was dan die van wiskundige Richard S. Hamilton, die eerder een oplossing had gesuggereerd. Een ander groot probleem dat het instituut opgelost wil zien, is het beroemde "P versus NP" en om het te proberen te begrijpen, is het meest gebruikelijke om naar het schaken te grijpen:
Wat is P versus NP?
Heb je er niets aan? Maak je geen zorgen, in het begin hielp het mij ook niet veel. P versus NP is ingewikkelder dan een paar koninginnen op een bord gooien, en zijn reputatie van onmogelijk is terecht. In zeer losse termen (en ik zeg "los" met alle oprechtheid) kunnen we zeggen dat de problemen die P worden genoemd gemakkelijk op te lossen en te verifiëren zijn met algoritmen, binnen een "polynomiale tijd".
Aan de andere kant zijn NP-problemen eenvoudig te verifiëren of hun oplossing correct is of niet, terwijl het bereiken ervan veel tijd en moeite kost, met aanzienlijke efficiëntieverliezen. Robuuste voorbeelden van NP-problemen zijn puzzels, Sudoku, en zelfs de Mijnenveger. Nu: wat zou er gebeuren als jij de sleutel vindt om een NP-probleem in polynomiale tijd en met grote efficiëntie op te lossen?
Als je dat lukt, zul je bewijzen dat er geen verschil is tussen N en NP (N = NP), waardoor het Clay Institute (en niet de Universiteit van St. Andrews) zoals tot vervelens toe herhaald een miljoen dollar jouw kant op gooit, waarschijnlijk gevolgd door een Nobelprijs, en de haat van cryptografie-experts over de hele wereld. De meeste experts neigen naar N ≠ NP, en eerlijk gezegd hangen veel dingen ervan af (de eerder genoemde cryptografie is er één). Maar als je het toch gaat proberen... succes. Je zult het nodig hebben.
