Augustus 2010

Het is nogal geestig om te zien waar mensen op zoeken voor ze op je blog terechtkomen. Hier zijn enkele zoektermen die horen bij recente schrijfsels:

• De oorlogspropaganda van de TIME: “vrouw neus Afghanistan”, “afghaanse vrouw verminkt”, “what happens if we leave afghanistan”.
• Satire over Bart De Wever en Elio Di Rupo: “bart de wever”, “vader van bart de wever”, “moeder bart de wever”, “bart de wever grootvader”, “grootvader bart dewever”, “genealogie bart de wever”, “moeder di rupo”, “elio di rupo genealogie”, “elio di rupo blog”, “reclamebureau nva”, “afbeelding karikatuur bart de wever en elio di rupo”.
• Kleuren: “politieke kleuren spa rood vld blauw cd&v oranje”, “grijsblauw verf mengen”, “kleuradvies verven in leuven”, “verfwinkel leuven”, “licht frequentie ratten”.
• Stemadvies: “stemtest 2010”, “voor wie moet ik stemmen stemtest 2010 verkiezingen nieuwsblad”, “hoe tactisch stemmen op nva”, “welke partij is tegen hoofddoekenverbod”, “energie nationaliseren”, “lsp groene energie”, “verkiezingen keuze test”, “politiek links rechts”, “politiek kompas blogs”, “lsp of pvda”, “pvda of lsp”, “lsp vs pvda”, “"front des gauches" ptb”.

Een aantal zoektermen die horen bij oudere dingen:

• Reisverhalen uit Amerika: “paedomorphose”, “kinderlijk leuven”, “amerikanen onbeleefd”, en uit Japan: “japanse supermarkt leuven” “vertraging openbaar vervoer japan” “japanse frisdrank”.
• Karikaturen maken van foto's: “getekende versie van foto gimp”, “karikaturen maken programma foto”, “zelf karikatuur maken van foto”, “the gimp karikatuur”, “karikaturen maken”, “distort cartoon gimp”, “gimp iwarp”.
• Pieter De Crem: “pieter de crem stemmen”, “karikatuur pieter de crem”, “belgische legerbasis afghanistan”,
• Marie-Rose Morel: “marie rose morel met hoofddoek”, “marie rose morel MIS AARDBEI”, “1992 Marie-Rose Morel”, “marie rose morel echtgenoot”, “kankerdagboek marie rose morel one line”.

Hieronder nog een aantal vreemde zoektermen waarmee je blijkbaar op deze blog kan uitkomen. Sommige mensen zoeken echt op rare dingen.

• “varken tekst”
• “fuck liberaal”
• “rechtse zakken”
• “armoede verbergen”
• “marxistische muziek”
• “evacuatie alarm mp3”
• “marxisme-katholicisme”
• “cijnskiesrecht cartoon”
• “K.U.Leuven natuurrampen”
• “luie werknemer karikatuur”
• “lelijke koppen verkiezingen”
• “wereldrecords exponentieel”
• “regering materie over hernia”
• “gsm frequentiebanden afghanistan”
• “teksten van op pensioen gaan met kleur”
• “hoe organiseer ik een betoging in brussel”
• “marxisme sterke schouders zwaarste lasten”
• “stellingen of manifestatie waar belgie te veel geld verspild”
• “emailadres van de broer van rector marc waer van kuleuven”

Vinay Deolalikar, een onderzoeker van Indische origine bij HP Labs in California, verstuurde op 6 augustus 2010 een draft van een bewijs dat P≠NP naar een aantal experten. Een dag later circuleerde het document op het internet en er woeden momenteel hevige internet-discussies erover. Als het bewijs juist is, of juist gemaakt kan worden, dan is het belangrijkste open probleem in de theoretische informatica opgelost — en krijgt Deolalikar 1 miljoen dollar (plus 200.000 dollar).

Er komt elke maand wel ergens iemand af met een poging tot bewijs van P=NP of P≠NP, maar met al die pogingen was er iets mis. Het is nog niet duidelijk hoe het zit met deze poging. De poging wordt in elk geval redelijk serieus genomen door een aantal “grote namen”. De voorlopige consensus lijkt te zijn dat er vanalles mee mis is, maar dat er mogelijk nog wel iets van te maken valt. De discussie kan je volgen op deze wiki.

Ik ga me niet wagen aan een uitspraak over deze poging tot bewijs. In de plaats daarvan zal ik hier uitleggen (voor leken) wat P≠NP betekent.

Beschouw problemen die te formuleren zijn als ja/nee-vragen over objecten. Bijvoorbeeld de vraag “Is dit een priemgetal?” over getallen, of de vraag “Is er een route van minder dan 1000 kilometer die alle steden passeert?” over (digitale voorstellingen van) landkaarten. Sommige problemen zijn moeilijker dan andere. Complexiteitstheorie is een onderdeel van theoretische informatica waarin bestudeerd wordt hoe moeilijk problemen zijn. De moeilijkheidsgraad wordt (tijds)complexiteit genoemd en wordt uitgedrukt als de hoeveelheid tijd die (met de best mogelijke oplossingsmethode, in het slechtste geval) nodig is om de ja/nee-vraag te beantwoorden voor objecten van een gegeven grootte.

De vraag “Is dit getal oneven?” kan je oplossen door gewoon naar het laatste cijfer te kijken, hoe lang het getal ook is. Dat is dus een gemakkelijk probleem: je kan het in constante tijd oplossen. De vraag “Is dit getal deelbaar door drie?” kan je oplossen door te kijken of de som van de cijfers deelbaar is door drie. Daarvoor moet je alle cijfers bekijken, dus je hebt meer tijd nodig naarmate het getal langer wordt. Het is nog altijd een gemakkelijk probleem: je kan het in lineaire tijd oplossen.

In de praktijk is er een groot verschil tussen problemen die in polynomiale tijd (constant, lineair, kwadratisch, kubisch, enzovoort) kunnen worden opgelost, en problemen waar meer tijd voor nodig is (exponentieel, facultair, enzovoort). Als een probleem in polynomiale tijd kan worden opgelost dan is het (meestal) in de praktijk op te lossen binnen een “redelijke” tijd, zelfs als de vraag gaat over een groot object. Als er echter bijvoorbeeld exponentiële tijd nodig is, dan is het probleem (meestal) in de praktijk onoplosbaar behalve voor hele kleine objecten. Voor sommige problemen weten we niet of ze in polynomiale tijd kunnen worden opgelost. Zo weten we nog niet zo lang dat je in polynomiale tijd kan bepalen of een getal priem is.

De verzameling van alle problemen die in polynomiale tijd oplosbaar zijn wordt P genoemd. De verzameling van alle problemen waarvoor ja-antwoorden in polynomiale tijd verifieerbaar zijn wordt NP genoemd. Verifiëren is gemakkelijker dan oplossen: gegeven het object en een “certificaat” moeten we controleren dat de oplossing juist is. Neem bijvoorbeeld de vraag of er een route van minder dan 1000km bestaat langs alle steden op een landkaart (het Travelling Salesman Problem). Men vermoedt dat dit probleem niet in P zit, en dus niet in polynomiale tijd kan opgelost worden. Het probleem zit wel in NP, want gegeven een route (dit is in dit geval het certificaat) kan je gemakkelijk in polynomiale tijd controleren of die route inderdaad alle steden aandoet en minder dan 1000km lang is.

Een alternatieve (maar equivalente) definitie van NP is de volgende: NP is de verzameling van alle problemen die in polynomiale tijd oplosbaar zijn op een niet-deterministische computer. Een niet-deterministische computer is een fictieve computer die de magische kracht heeft om altijd juist te gokken: als er een keuze moet gemaakt worden (bijvoorbeeld: welke stad is de volgende op mijn route?) dan kiest deze computer altijd “juist”. Anders geformuleerd: op het moment dat er een keuze moet gemaakt worden tussen A en B, kan deze computer zich opsplitsen in twee computertjes, waarbij computer 1 kiest voor A en computer 2 kiest voor B. Elk van die computertjes kunnen zich verder opsplitsen, enzovoort. Als er uiteindelijk één computertje tot een oplossing is gekomen, dan roept die heel hard “ja!” en worden alle andere computertjes weggegooid. Alleen als alle kleine computertjes “nee” zeggen dan wordt het antwoord “nee” gegeven.

Het is duidelijk dat P⊆NP. Alle problemen die in polynomiale tijd oplosbaar zijn, zijn ook in polynomiale tijd verifieerbaar (je hebt zelfs geen certificaat nodig; je lost gewoon het probleem zelf op bij wijze van verificatie). Of als je de andere definitie van NP verkiest: alle problemen die in polynomiale tijd oplosbaar zijn op een gewone computer, zijn ook in polynomiale tijd oplosbaar op zo'n magische niet-deterministische computer (die magische computer splitst zich gewoon nooit op).

De kwestie is dus, is het zo dat P=NP, of is P≠NP? Het algemeen vermoeden is dat P≠NP, m.a.w. dat er dingen zijn die een fictieve “magische” niet-deterministische computer kan maar een gewone computer niet. Computerwetenschappers proberen nu al ongeveer een halve eeuw om dat vermoeden te bewijzen (of te weerleggen). Er is een mogelijkheid dat het vermoeden nu bewezen kan worden op basis van de ideeën van Deolalikar. Maar het zou ook goed kunnen dat deze poging tot bewijs waardeloos blijkt te zijn en dat we binnen een halve eeuw nog geen stap verder staan. Ik ben benieuwd wat het zal worden...