Sommige Problemen Zijn Moeilijker Dan Andere
Vrij naar Ben Brubaker
Waarom zijn sommige problemen moeilijker dan andere? Het klinkt als het soort vraag dat zou kunnen opkomen bij een hoofdvakstudent filosofie die vastloopt door de tweede helft van een wiskundetoets, maar het is eigenlijk een van de meest diepgaande vragen in de informatica, die een vakgebied aanstuurt dat computationele complexiteitstheorie wordt genoemd. In de afgelopen vijftig jaar heeft onderzoek naar de complexiteitstheorie inzichten opgeleverd in de fundamentele aard van berekeningen, maar ook in praktische toepassingen in cryptografie, parallel computergebruik en vele andere gebieden.
Complexiteitstheoretici bestuderen problemen die in principe kunnen worden opgelost met behulp van stapsgewijze procedures, oftewel algoritmen. Dit worden rekenproblemen genoemd, maar ze hebben niet noodzakelijkerwijs iets met computers te maken. Het alfabetiseren van uw boekenplank is bijvoorbeeld een rekenprobleem, en er zijn veel algoritmen die u kunt gebruiken om dit op te lossen. Hier is er één: plaats alle boeken in willekeurige volgorde op de plank, veeg ze vervolgens weg en probeer het opnieuw totdat je het precies goed hebt. Er is geen doctoraat in de computerwetenschappen voor nodig om te weten dat vrijwel elke andere strategie de klus sneller zal klaren.
Wanneer complexiteitstheoretici het hebben over het verschil tussen gemakkelijke en moeilijke problemen, maken ze eigenlijk een onderscheid tussen snelle en langzame algoritmen. Net als bij het alfabetiseren van een plank kunnen de meeste rekenproblemen worden opgelost met behulp van veel verschillende algoritmen. Als ten minste één van die algoritmen snel is, noemen onderzoekers het probleem eenvoudig. Als niemand snelle algoritmen heeft ontdekt om een probleem op te lossen, betekent dit dat het probleem moeilijk is.
Veel belangrijke rekenproblemen vallen in deze laatste categorie. Decennia lang hebben onderzoekers gezocht naar snelle algoritmen voor dergelijke problemen en kwamen ze met lege handen terecht, maar ze hebben de mogelijkheid van onontdekte snelle algoritmen niet categorisch kunnen uitsluiten. Zijn deze problemen echt moeilijk of niet?
Dat is de essentie van het P versus NP-probleem, een fascinerende vraag vervloekt met een uitzonderlijk saaie naam. Het is eigenlijk een vraag over twee brede klassen van rekenproblemen: “P” verwijst naar de klasse van alle gemakkelijke problemen, terwijl “NP” de klasse van problemen is die wel of niet gemakkelijk op te lossen zijn, maar wel snelle algoritmen hebben voor het controleren of een kandidaat-oplossing correct is. De vraag van een miljoen dollar is of deze twee klassen daadwerkelijk gelijkwaardig zijn – dat wil zeggen: of er een gemakkelijke manier is om elk probleem op te lossen waarvan de oplossing gemakkelijk te controleren is.
Zo gezegd, de vraag klinkt eenvoudig. Maar in feite is het landschap van computationele hardheid veel rijker dan complexiteitstheoretici zich hadden voorgesteld toen ze voor het eerst het P versus NP-probleem stelden.
Wat is nieuw en opmerkelijk
Complexiteitstheoretici worstelen nu al een halve eeuw met de P versus NP-vraag, en het antwoord blijft ongrijpbaar: het lijkt erop dat dit probleem over de hardheid van computationele problemen zelf moeilijk op te lossen is.
Dat zelfreferentiële karakter is onderzoekers niet ontgaan. Afgelopen zomer heb ik een diepe duik genomen in de verbijsterende wereld van metacomplexiteit: de studie van de hardheid van computationele problemen die zelf over de hardheid van computationele problemen gaan. “Als je er niet zeker van bent, maak je dan geen zorgen – ik ben ook in de war”, stelde complexiteitstheoreticus Igor Oliveira me gerust tijdens een interview. De afgelopen jaren hebben onderzoekers ontdekt dat ogenschijnlijk geheimzinnige meta-complexiteitsproblemen nauw verbonden zijn met de vraag of enige vorm van encryptie echt veilig kan zijn.
De complexiteitstheorie omvat meer dan het onderscheid tussen gemakkelijke en moeilijke problemen; onderzoekers onderzoeken ook veel verschillende smaken van rekenhardheid. Soms betekent dat het bestuderen van subtielere verschillen in moeilijkheidsgraad tussen NP-problemen. Voor een handvol bijzonder frustrerende problemen hebben onderzoekers geen betere algoritmen ontdekt dan simpelweg elke mogelijke oplossing te controleren. Vorige maand schreef ik over hoe twee teams van onderzoekers een iets sneller algoritme ontdekten voor een probleem waarvan lang werd gedacht dat het in deze categorie zou vallen. Het nieuwe algoritme werkt door technieken aan te passen die zijn ontwikkeld om encryptieprotocollen aan te vallen – een mooie illustratie dat ideeën in beide richtingen kunnen vloeien tussen complexiteitstheorie en cryptografie.
Andere onderzoekers onderzoeken problemen die veel, veel moeilijker zijn dan die in NP – bijna tot op het punt van absurditeit. In deze gevallen is er geen voor de hand liggende manier om te controleren of een voorgestelde oplossing correct is, of zelfs om alle mogelijkheden op te sommen. Onlangs hebben onderzoekers bewezen dat een onschuldig klinkend probleem eigenlijk een van de moeilijkste is (behalve de problemen die letterlijk onoplosbaar zijn). Een dergelijk bizar probleem lijkt misschien ver verwijderd van welke praktische toepassing dan ook, maar het komt naar voren in de studie van concurrent computing, waarbij programma's taken in vele kleine delen verdelen en er tegelijkertijd aan werken.
Dit zijn slechts enkele van de recente resultaten in de complexiteitstheorie; onderzoekers in het veld hebben ook het gebruik van willekeur onderzocht, de aard van wiskundig bewijs en meer. “P versus NP is net als onze hoeksteen ergens midden in een tempel”, vertelde de wiskundige en complexiteitstheoreticus Alexander Razborov me vorig jaar. "De tempel is enorm groot en produceert veel coole dingen."
Afbeeldingen gegenereerd door you.com met query 'complexity computations'