In wiskunde hebben we te maken met verschillende soorten problemen. Op de basisschool beginnen we met 1+1 en dat rekenden we uit met behulp van snoepjes. Iets later in onze basisschoolcarrière leerden we breuken door middel van een taart in stukken verdelen. Zo beetje bij beetje leren we steeds moeilijkere wiskundige problemen, maar hoe bepaal je nou precies de moeilijkheidsgraad van een wiskundig probleem? Waarom is 1+1 makkelijker dan ?
 

De complexiteitsgraad

Om wiskundige problemen in klassen uit te drukken is er de complexiteitsgraad. De complexiteitsgraad van een bepaald algoritme is de manier waarop het algoritme zich gedraagt als de grootte van het op te lossen probleem toeneemt. Uit de complexiteitsgraad komt de complexiteitstheorie voort. De computationele  complexiteitstheorie classificeert problemen in een aantal categorieën die de inherente moeilijkheidsgraad aangeven van deze problemen. Een probleem wordt gezien als moeilijk als het voor alle algoritmes veel tijd of geheugen in beslag neemt.
In de groeispurt van de wiskunde, zo rond de jaren 20 en 30 van de vorige eeuw, is de complexiteitstheorie ontstaan. Echter jaren daarvoor bewees Gödel dat in iedere theorie van voldoende complexiteit altijd stellingen bestaan die onbewijsbaar zijn. Daardoor gingen wiskundigen vol overtuiging op zoek naar de grens: wat is wel bewijsbaar, wat niet? Om deze vraag te beantwoorden moesten de wiskundigen eerst vaststelling wat een berekening precies is. Het is namelijk bijna onmogelijk om te bedenken wat we doen als we een berekening uitvoeren. Iedereen weet 1+1=2, maar wat gebeurt er in onze hersenen, dat we er 1 en 1 instoppen en 2 eruit komt?
De oplossing hiervoor was een schema om te zien hoe een berekening precies verloopt. In 1936 publiceerde Alan Turing zijn Turing-machine; een van de eerste berekeningsmodellen om zo’n schema te visualiseren. Precies in dezelfde tijd publiceerde Alonzo Church zijn eigen berekeningsmodel, de lambdacalculus. Er ontstond een hevige strijd tussen de heren Church en Turing, beide wilden aantonen dat hun model in staat was het grootste aantal problemen en algoritmes tot uitdrukking te brengen. Uiteindelijk werd er besloten dat het gelijkspel was. Het intrede van deze berekeningsmodellen zorgden voor een heel nieuw deel van de wiskunde namelijk: de complexiteitstheorie.

De opmars van de Turing-Machine

In de jaren daarna won de Turing-machine veel terrein in de wiskunde. Dit had als reden dat de Turing-machine een algoritme heel mechanisch beschrijft; een algoritme wordt tot in de meest kleinste stapjes uitgeschreven. Beide modellen waren echter in staat om te zeggen of een algoritme wel of niet berekenbaar is, maar de Turing-machine ging toch een stapje verder. Het model kon ook antwoord geven op de vraag hoe lang een bepaalde berekening duurde. Daardoor ontstond het tweede gedeelte van de complexiteitstheorie: het gedrag van algoritme. De Turing-machine bleek al snel ook elektronisch uitvoerbaar, waardoor de eerste computer tot leven kwam. De manier waarop de Turing-machine een algoritme beschrijft wordt ook wel tijdscomplexiteit genoemd, omdat er gekeken wordt naar hoeveel stappen er nodig zijn om een probleem op te lossen. Naast tijdscomplexiteit is er ook ruimtecomplexiteit, dit betreft de relatie tussen de grootte van het probleem en de hoeveelheid geheugen er bij de berekening wordt gebruikt. Als we spreken over complexiteit, is dit vaak tijdscomplexiteit.

Feit: In de tweede wereldoorlog werd de Turing-machine gebruikt in Groot-Brittannië om Duitse codes te breken

Focus van de complexiteitstheorie

De complexiteitstheorie houdt zich nog altijd bezig met de classificatie van algoritme in moeilijkheid en tevens waar de grens ligt tussen berekenbaar en onberekenbaar, makkelijk of moeilijk berekenbaar. De theorie bekijkt de problemen echter in de algemenere zin, en niet alleen individuele problemen. Neem bijvoorbeeld een sommatie van twee natuurlijke getallen, dan kun je al oneindig veel problemen bedenken.  Daarnaast is het bekijken van iedere individuele optelling ook niet erg interessant.
De complexiteitstheorie focust zich meer om het bepalen van de complexiteit van klassen problemen tegelijk en niet zozeer naar de complexiteit van problemen op zichzelf. De theorie zou bijvoorbeeld niet focussen op “wat is de complexiteit van het oplossen van 4+5”, maar op “wat is de complexiteit van een algemene methode om een sommatie van twee natuurlijke getallen op te lossen”.
Echter dat de algemene methode van oplossen hetzelfde is, betekent niet dat er direct een uitspraak kan worden gedaan over de complexiteit van een hele klassen van problemen. Bijvoorbeeld het uitvoeren van het product duurt langer dan . Daarom drukt de complexiteitsgraad de complexiteit van een probleem uit in de termen van het aantal stappen dat een gegeven algoritme nodig heeft ten opzichte van de grootte van de invoer, om toch een uitspraak te kunnen doen over de complexiteit van algoritmes. Wel is hiervoor een concept van “grootte” nodig, echter is dat geen probleem voor de Turing-machine; dit model is zo dat iedere invoer een grootte moet hebben, het benodigde aantal posities op de band. Het aantal stappen dat een algoritme moet zetten om tot een oplossing te komen, ten opzicht van de grootte van de invoer is nu de complexiteit van het algoritme. Bijvoorbeeld, als een invoer de grootte  heeft, dan zou gezegd kunnen worden dat de complexiteit van een gegeven algoritme gelijk is 
 
Deze manier van uitdrukken van complexiteit leidt voor ieder algoritme A tot een uitdrukking van die complexiteit C(A). Hierdoor wordt het mogelijk om verschillende complexiteiten van algoritmes met elkaar te vergelijken. Naast een directe vergelijking, kan er ook gebruik worden gemaakt van een wat grovere indeling naar complexiteit van algoritmes, dit wordt ook wel grootte-ordes genoemd. De grootte-ordes hebben het voordeel dat ze de algoritmes in deze langs grote lijnen en dat hierdoor een overzichtelijke hiërarchie van klassen van algoritmen onstaat, echter zijn ze niet erg precies. Er wordt alleen gekeken naar het van de uitdrukking van C(A), dat C(A) het meest bepaald. Eerder hadden we de uitdrukking dat de complexiteit van een algoritme gelijk was aan , dan zou in dit geval de grootte-orde gelijk zijn aan  en het algoritme is kwadratisch qua grootte-orde.
Er zijn verscheidene manieren om grootte-ordes voor algoritmes te weergeven. Hierbij wordt alleen gebruikgemaakt van een polynomiale uitdrukking. Echter hebben ze wel allemaal een eigen betekenis en een eigen idee.
 
 

P en NP problemen

Als laatste kenmerkt de complexiteitstheorie zich ook door de scheiding tussen makkelijke en moeilijke problemen. De makkelijke problemen worden gekenmerkt door een algoritme met een tijdscomplexiteit, die een polynomiale uitdrukking is in de grootte van de invoer. Samen vormen zij de verzameling P, wat voort komt uit in polynomiale tijd oplosbare problemen. Voor de moeilijke problemen geldt dat er niet zo’n algoritme bekend is. Voor een gros van de problemen is zo’n algoritme niet snel bekend en van een deel is bewezen dat zo’n algoritme niet kan bestaan. Wel kan er gezegd worden over een groot aantal van deze problemen dat er algoritmen bekend zijn, maar er kan niet met zekerheid gezegd worden dat dit de beste oplossingen zijn. Naast deze heuristische problemen is er een klasse die wordt gevormd door de niet-deterministische polynomiaal problemen. Voor veel van deze problemen is er geen polynomiaal algoritme bekend, echter is er voor alle NP problemen een gegeven kandidaat-oplossing, die in polynomiale tijd gecontroleerd kan worden op correctheid.
 
In de NP problemen klasse vormen de NP-volledig problemen een bijzondere groep. NP-volledig problemen zijn problemen die binnen de NP klasse vallen en waarvan elk ander probleem in de NP klasse in polynomiale tijd naar dit probleem kan worden gereduceerd. Dit wil zeggen, als je een algoritme hebt om een enkel NP-volledig probleem op te lossen, je dit algoritme kan gebruiken om ieder probleem in NP op te lossen. Als er dus zo’n algoritme wordt gevonden voor een NP-volledig probleem, kun je daarmee alle NP problemen in polynomiale tijd worden opgelost, waardoor de verzameling NP gelijk is aan P. Een voorbeeld van een NP-volledig probleem is het handelsreizigersprobleem.
Dit vraagstuk is een van de zeven Millennium Prize Problems die zijn uitgeroepen door het Clay Mathematics Institute in 2000. Voor het oplossen van dit probleem krijgt de winnaar een miljoen euro. De meeste wiskundigen en computer geleerden verwachten dat de verzameling P niet gelijk is aan de verzameling NP.

“If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in ‘creative leaps,’ no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss…”— Scott Aaronson, MIT

Dit artikel is geschreven door Noortje Stolk