Wat is voor een handelsreiziger de goedkoopste manier om elke hoofdstad van de landen van Europa precies één keer aan te doen tijdens zijn dienstreis? Dat is grofgezegd het befaamde Handelsreizigersprobleem, een vraag die simpel lijkt maar een van de hardnekkigste problemen uit de complexiteitstheorie is.
Een 26 jaar oude claim voor de oplossing van het probleem is eindelijk definitief ontkracht door onderzoekers van het Centrum Wiskunde & Informatica (CWI) in Amsterdam, de Université Libre de Bruxelles en de Friedrich-Alexander Universität Erlangen-Nürnberg. De onderzoekers presenteerden hun resultaten op het Symposium on Theory of Computing 2012 in New York. Voor hun werk deelden ze de Best Paper Award van het symposium.
De vraag hoe moeilijk het Handelsreizigersprobleem is, is één van de grootste onopgeloste problemen in de wiskunde en informatica. Als de handelsreiziger maar drie steden – zeg Amsterdam (A), Berlijn (B) en Chisinau (C ) – moet bezoeken, is het probleem nog overzichtelijk: als begin- en eindpunt hetzelfde zijn (zeg Amsterdam), zijn er maar twee mogelijke routes: ABCA en ACBA. Met een vierde stad – Dublin (D) – erbij zijn er zes mogelijkheden: ABCDA, ABDCA, ACBDA, ACDBA, ADBCA en ADCBA.
In het algemeen: als er n steden zijn, dan zijn er (n – 1)! = (n – 1) x (n – 2) x (n – 3) x … x 3 × 2 × 1 mogelijke routes. Deze getallen worden al gauw onbeheersbaar groot. Als er 26 steden zijn, is er geen computer die in staat is om de kosten van elke mogelijke route te berekenen. Er zouden 25! ≈ 1,55 × 1025 kostenberekeningen uitgevoerd moeten worden. Een computer die 1012 van zulke berekeningen per seconde kan uitvoeren, doet daar zo’n 500.000 jaar over!
P versus NP
Tot op de dag van vandaag is er voor het Handelsreizigersprobleem geen ideale oplossingsmethode gevonden. Wiskundigen en informatici zoeken al jaren naar een efficiënte oplossing voor dit probleem. Dit zou namelijk een positief antwoord betekenen voor de beroemde vraag of P gelijk is aan NP. P staat voor de verzameling van problemen die ‘makkelijk’ zijn. Dat wil zeggen: om een P-probleem op te lossen, is een rekentijd nodig die slechts geleidelijk toeneemt met het groter worden van het probleem (in het geval van het Handelsreizigersprobleem: het toenemen van het aantal te bezoeken steden). Het sorteren van een lijst getallen op grootte is een voorbeeld van een P-probleem: de rekentijd neemt ongeveer evenredig toe met de lengte van de lijst.
Dan zijn er ook nog de zogeheten NP-problemen. Dat zijn problemen waarvan een oplossing te verifiëren is in een korte rekentijd, terwijl het er niet toe doet wat de tijd is die nodig is om aan die oplossing te komen. Elk P-probleem is dus ook een NP-probleem: voor een probleem waarvan de oplossing ‘snel’ kan worden gevonden, geldt zeker dat die oplossing ‘snel’ kan worden geverifieerd. Interessant zijn de andere NP-problemen, problemen waarvoor we geen methode kennen om snel op te lossen. De rekentijd om dergelijke problemen op te lossen, groeit exponentieel met het groter worden van het probleem.
De categorie NP bevat een onderafdeling, NP-volledig geheten. Die problemen hebben de bijzondere eigenschap dat ze in feite allemaal hetzelfde zijn, want er bestaat een efficiënte methode om ze naar elkaar te vertalen. Dus als je voor één NP-volledig-probleem een efficiënt algoritme vindt, werkt dit bij allemaal. Het Handelsreizigersprobleem is zo’n NP-volledig probleem.
Als iemand een efficiënte oplossing voor het Handelsreizigersprobleem (of een ander NP-volledig probleem) vindt, betekent dit dat P gelijk is aan NP: elk probleem waarvan de oplossing snel door een computer te controleren is, kan ook snel door een computer worden opgelost. Als dit waar zou zijn, heeft het grote gevolgen. Complexe problemen in bijvoorbeeld planning, logistiek en bioinformatica zijn dan snel op te lossen en de wetenschappelijke ontwikkeling zou in een stroomversnelling komen.
Het P-versus-NP-probleem is een van de zeven millenniumproblemen van het Amerikaanse Clay Mathematics Institute, dat een miljoen dollar klaar heeft liggen voor degene die het oplost.
‘(Niet-)symmetrische’ lineaire programma’s
De meeste experts geloven echter dat P ongelijk is aan NP. Desondanks duiken er regelmatig claims op van ‘bewijzen’ dat P=NP. Vaak zijn ze eenvoudig te weerleggen, maar soms ook niet. De CWI-onderzoekers en hun Belgische en Duitse collega’s ontkrachten in hun artikel een bewijsvoorstel dat al uit de jaren ’80 stamt.
“In 1986 claimde de Canadese wiskundige Ted Swart dat hij het Handelsreizigersprobleem – wat is de kortste route die door n steden gaat, en die eindigt waar die begon? – snel kon oplossen met een zogenaamd lineair programma. Dit zorgde voor grote opwinding in de wiskundige wereld, maar al snel bleek niemand zijn resultaten te kunnen verifiëren,” zegt Ronald de Wolf van het CWI. Een lineair programma minimaliseert een functie (in dit geval de lengte van de route) over een oplossingsruimte die bepaald wordt door lineaire constraints. Een lineair programma is ‘symmetrisch’ wanneer het alle steden symmetrisch behandelt, dat wil zeggen dat de oplossingsruimte niet verandert wanneer je de namen van de n steden door elkaar husselt.
Na ongeveer een jaar bewees Mihalis Yannakakis dat zogeheten symmetrische lineaire programma’s zoals die van Swart überhaupt niet in staat zijn om het Handelsreizigersprobleem snel op te lossen, hij bewees namelijk dat je exponentieel veel constraints nodig hebt om de oplossingsruimte te beschrijven. Hierdoor kunnen deze lineaire programma’s niet efficiënt worden opgelost, ze zijn gewoon veel te groot.
Het idee om lineaire programma’s te gebruiken bleef echter bestaan, maar dan de niet-symmetrische lineaire programma’s. “Nu, 26 jaar na de claim van Swart, hebben wij aangetoond dat lineaire programma’s in het geheel niet in staat zijn om het Handelsreizigersprobleem snel op te lossen, zelfs niet wanneer ze niet-symmetrisch zijn,” aldus De Wolf. “Dat is belangrijk,” vervolgt hij, “want voor sommige andere optimalisatieproblemen bestaan geen efficiënte symmetrische lineaire programma’s, maar wel efficiente niet-symmetrische lineaire programma’s. Wij hebben dus bewezen dat dit laatste voor het Handelsreizigersprobleem niet het geval is.”
Kennislinkartikelen over NP-volledige problemen:
Oeps: Onbekende tag `feed’ met attributen {"url"=>"https://www.nemokennislink.nl/kernwoorden/np-probleem.atom", “max”=>"10", “detail”=>"minder"}