Complexiteitstheorie
Van Wikipedia
| Principes |
| Complexiteitstheorie |
| Modellen |
| Algoritme |
| Turingmachine |
| Lambdacalculus |
| Theorieën |
| Berekenbaarheid |
| Complexiteitsgraad |
| NP-compleet |
De complexiteitstheorie is het gebied van wetenschappelijk onderzoek dat zich bezighoudt met de vragen welke wiskundige problemen al dan niet oplosbaar zijn en hoe efficiënt oplossingen voor een gegeven probleem zijn.
De complexiteitstheorie is een overlapgebied van de wiskunde en de informatica. Het is ook een van de oudste pijlers waarop de informatica als vakgebied en wetenschap gebaseerd is en het is niet onredelijk om te zeggen dat de informatica uit de vraagstukken van de complexiteit ontstaan is.
[bewerk] Geschiedenis
De complexiteitstheorie is ontstaan in de jaren '20 en '30 van de 20e eeuw. Die decennia vormden het hoogtepunt van een enorme "groeispurt" in de wiskunde, die begonnen was rond 1870.
Sinds 1870 had de wiskunde zichzelf getransformeerd van een verzameling losse rekentechnieken tot een abstracte wetenschap, een geheel van principes, axioma's, taalstructuren en filosofische inzichten. Achtereenvolgende publicaties van Peano, Dedekind, Frege, Whitehead en Russell hadden een geheel van theorie en begrip opgebouwd waardoor het leek of er aan de mogelijkheden geen einde zou komen.
Aan het begin van de 20e eeuw vond de wiskunde echter zijn eigen limieten, in de vorm van het werk van Gödel, die bewees dat in iedere theorie van voldoende complexiteit altijd stellingen bestaan die onbewijsbaar zijn.
Deze vaststelling was voor wiskundigen echter in het geheel geen domper. In plaats daarvan wierpen wiskundigen zich vol overgave op de vraag waar de waterscheiding lag – wat was wel bewijsbaar, wat niet? Wat kon berekend worden en wat niet?
Het begin van het antwoord op die vragen begon zich rond 1936 te vormen. Vrijwel vanaf het eerste moment dat de vraag gesteld werd of een probleem oplosbaar was of niet, was duidelijk dat die vraag alleen beantwoord kon worden door eerst vast te stellen wat een berekening precies is. Hoe verloopt een berekening? Wat doen we precies, als we een berekening uitvoeren? Het is uiteraard heel leuk om uit het hoofd te kunnen zeggen "2 + 2 = 4", maar wat gebeurt er dan precies in ons hoofd dat we er 2 en 2 in stoppen en er 4 uit komt rollen?
In 1936 publiceerde Alan Turing zijn Turing-machine, een van de eerste berekeningsmodellen: een schema van hoe een berekening precies verloopt. Rond dezelfde tijd publiceerde Alonzo Church een totaal ander berekeningsmodel, de lambdacalculus. De publicaties resulteerden in een spectaculair "wedstrijdje" tussen Church en Turing om aan te tonen welk model in staat was het grootste aantal problemen en algoritmen tot uitdrukking te brengen (wat wij nu expressiviteit van een model noemen).
Na het einde van de "tweestrijd" (besloten in een wonderbaarlijk gelijkspel), gaf de introductie van de berekeningsmodellen aanleiding tot een heel nieuwe tak van wiskundige sport: de complexiteitstheorie. Met name het model van Turing leende zich erg goed voor het onderzoek dat centraal staat in deze wetenschap, omdat Turings model een algoritme heel mechanisch beschrijft: in termen van de kleinst mogelijke stappen, heel precies, in de vorm van "eerst doe je dit en dan doe je dat". Beide modellen van berekening maakten het mogelijk om een antwoord te geven op de vraag wat wel en niet berekenbaar is. Turings model maakte echter ook de vraag mogelijk hoe lang een bepaalde berekening dan wel niet duurt. Hiermee ontstond de tweede, centrale vraag van de complexiteitstheorie: het gedrag van algoritmen.
Turings model van berekening won zeer snel daarna enorm aan betekenis buiten de harde wiskunde. In 1939 brak de Tweede Wereldoorlog uit en Groot-Brittannië had behoefte aan een manier om snel Duitse codes te breken. Turings berekeningsmodel bleek al snel uitstekend uitvoerbaar in een elektrische machine – de eerste computer was geboren. Na de oorlog bleef de fascinatie voor de mogelijkheden van Turings machine bij velen hangen. Overal ter wereld begonnen wiskunde-faculteiten zich ermee bezig te houden. Uiteindelijk zozeer dat de studie van de mogelijkheden van de machine een eigen leven ging leiden en een eigen naam kreeg: de informatica.
Tegenwoordig houdt de complexiteitstheorie zich nog altijd bezig met de classificatie van algoritmen naar graad van complexiteit en met de vraag waar de grens precies ligt tussen berekenbaar en onberekenbaar en tussen makkelijk berekenbaar en moeilijk.
Belangrijk: de complexiteitstheorie heeft zijn weg ook gevonden naar andere wetenschappen. Zo lijkt de paradigmatische kijk ook zeer bruikbaar te zijn in bijvoorbeeld de sociologie.
[bewerk] Principes
Stel, er is een wiskundig probleem Q.
De centrale vragen van de complexiteitstheorie ten opzichte van Q kunnen nu als volgt gedefinieerd worden:
- Bestaat er een algoritme dat Q oplost?
- Zo ja, hoe gedraagt dit algoritme zich dan?
- Zo nee, kunnen we dan bewijzen dat die oplossing niet kan bestaan, of moet hij er wel zijn en hebben we de oplossing alleen nog niet gevonden?
Het begin van het beantwoorden van deze vragen ligt in het kunnen geven van een precieze beschrijving van een berekening. Kan dat niet, dan hebben we totaal geen houvast om iets te kunnen zeggen over de antwoorden op bovenstaande vragen.
Het beschrijven van berekeningen gebeurt door middel van zogeheten berekeningsmodellen, stap-voor-stap beschrijvingen van wat er gebeurt om een berekening plaats te laten vinden. De meeste bekende berekeningsmodellen zijn de Turing-machine en de lambdacalculus. De eerste geeft een zeer laag-niveau beschrijving van berekeningen in de vorm van een stappenplan met hele kleine stappen. De stappen werken op precies beschreven wijze, op invoer van precies beschreven vorm en produceren al dan niet antwoorden van precies beschreven vorm. Het tweede model is veel abstracter en beschrijft berekeningen in termen van veel hogere, meer samenvattende concepten. De modellen hebben allebei een heel eigen manier om algoritmen tot uitdrukking te brengen en lijken vrijwel in niets op elkaar. Een zeer opmerkelijk resultaat van de vroege complexiteitstheorie is dan ook het volgende:
- Qua expressiviteit (de mogelijkheid van een model om een algoritme tot uitdrukking te brengen) zijn de Turing-machine en de lambdacalculus gelijk aan elkaar
Turing bewees dit op zeer elegante wijze door een algoritme te verzinnen dat een beschrijving in het ene model omschrijft in een beschrijving in het andere model en omgekeerd.
Van beide modellen bestaat het (onbewijsbare) vermoeden dat zij in staat zijn elke, mogelijke berekening te beschrijven. Wat niet beschreven kan worden (is het vermoeden) is niet berekenbaar. Uiteraard is het een open vraag of dit waar is en dus ook een onderwerp van veel onderzoek. Dit vraagstuk wordt het vraagstuk van de berekenbaarheid genoemd.
Het Turing-model beschrijft een algoritme mechanisch, in kleine stappen. Het aantal stappen wordt daarmee een maat voor hoe lang een berekening duurt. Het blijkt in de context van de Turing-machine dat er een hele hiërarchie bestaat van algoritmen – een uitgebreide indeling van "snelle" of "makkelijke" algoritmen tot en met "langdurige" of "moeilijke" algoritmen, met beschrijvingen van maximale en minimale doorlooptijden. Gemeten ten opzichte van de grootte van de invoer overigens, want anders kun je de snelheid (of ook: eficiëntie) van een "snel" algoritme door middel van grote invoer zo erg oppompen dat het algoritme meer tijd nodig heeft dan een "langzaam" algoritme met kleine invoer. Deze eigenschap van algoritmen wordt de complexiteitsgraad van een algoritme genoemd.
