Dick van Leijenhorst: Complexiteit

Complexiteitstheorie - de Formule 1 van de Informaticatheorie

Dick van Leijenhorst

Tot de meest frustrerende verschijnselen als je achter je computer zit behoort het crashen of het "niet stoppen" van je programma. Dat laatste kan allerlei oorzaken hebben: het komt bijvoorbeeld in een "oneindige lus" terecht. Maar, het kan ook zo zijn dat het wel ooit stopt, maar misschien na een jaar, of 100 jaar.

Informatica aan de Universiteit is niet alleen maar het bouwen of gebruiken van toepassingen: die doen dus vaak niet wat je bedoelt en bij ons leer je ook na te denken waar dat aan kan liggen.

De Complexiteitstheorie nu, houdt zich bezig met het analyseren van computertaken met betrekking tot hun snelheid, en zonodig met het "opvoeren"! (Het eerste wat je daarbij trouwens leert is dat het voor de echt moeilijke problemen nauwelijks uitmaakt om een snellere computer aan te schaffen.)

Een beroemd voorbeeld van versnelling is de FFT, een programma dat gebruikt wordt voor heel diverse taken zoals het analyseren van getijdebewegingen, toepassingen in de kristallografie, en het comprimeren van plaatjes. J.W. Cooley en John Tukey werden in 1965 wereldberoemd toen ze een manier vonden om de toenmalige methoden ontzettend te versnellen, soms wel een factor 800000. Ze gebruikten de zgn. "verdeel- en heers methode" uit de complexiteitstheorie waarbij een moeilijk probleem op een slimme manier in kleinere deeltjes wordt gehakt. Zonder dit geen digitale ICT!

Een uitleg (in het Engels) van een iets eenvoudiger geval, namelijk een beroemde versnelling van "gewoon" rekenen, kun je vinden op http://www.cs.ru.nl/~bolke/Poster.html

Een ander probleem waar je tegenaan kunt lopen: je werkt ergens, en je baas komt met een computerklus die niet doenlijk lijkt: als de invoer een beetje realistische grootte heeft sta je te wachten tot Sint Juttemis (of de zaak loopt vast).

Valt dit enigszins te voorspellen? Nu, de Complexiteitstheorie heeft een onderafdeling waarin programma's ingedeeld worden naar hun moeilijkheidsgraad (in zgn. complexiteitsklassen). Er bestaan zulke problemen (zgn. NP-complete) waarvoor het weinig praktische zin heeft om ze met klassieke methoden te proberen op te lossen. Er bestaan technieken om het probleem van je baas aldus in te delen, waarna jij in ieder geval niet de schuld krijgt van de lange verwerkingstijd! Moderne cryptografie (gegevensbeveiliging) is volledig geïnspireerd door de Complexiteitstheorie. Het doel is, "moeilijke" problemen in bovenstaande zin, zodanig te gebruiken dat je daarmee boodschappen kunt versleutelen tot schijnbare nonsens, waarbij het zonder extra "sleutel"-informatie ondoenlijk is de boodschap te reconstrueren. Een uitleg van complexiteitsklassen en wat cryptografische toepassingen kun je vinden op http://www.cs.ru.nl/~bolke/ bartjens.pdf. Het is een stukje voor eerstejaars wiskundigen.

Een laatste voorbeeld. Op elke computer staan wel toepassingen om bestanden kleiner te maken (bv. te Gzippen). Heb je er wel eens over nagedacht of je daar maar mee door kunt gaan? Natuurlijk niet; je kunt niet drie verschillende boeken elk tot één bit samenpersen - want dan kun je daarna ze niet meer uitpakken tot drie verschillende boeken. Hoever kun je een rij symbolen eigenlijk comprimeren? Kan dat altijd wel? Waarom ziet een ingepakt bestand er zo chaotisch uit? Ook dit is zijn complexiteitsproblemen met allerlei uitdagende vertakkingen en toepassingen.

In de Complexiteitstheorie komen zowel diepe inzichten als praktische toepassingen aan bod, en er zijn verbanden met vrijwel elk deelgebied van de Informatica. Theorie hoeft niet saai te zijn!

---

Hier nog een langer verhaal erover: http://www.cs.ru.nl/~erikpoll/voorlichting/Dick_bartjens.pdf