Het handelsreizigersprobleem is nog altijd niet opgelost. 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 Vrije Universiteit Brussel en de Friedrich-Alexander Universität Erlangen-Nürnberg. De onderzoekers presenteerden hun resultaten deze week op het Symposium on Theory of Computing 2012 (STOC’12) 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. Het vraagstuk gaat over een handelsreiziger die de kortst mogelijke weg door een gebied zoekt die hem precies één keer langs elke stad brengt. 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. Deze gelijkheid beweert dat elk probleem waarvan de oplossing snel door een computer te controleren is, ook snel door een computer opgelost kan worden. 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.
De P=NP vraag is waarschijnlijk het belangrijkste probleem in de theoretische informatica. Het is ook een van de zeven Millenium Prize Problems van het Amerikaanse Clay Mathematics Institute, dat een miljoen dollar klaar heeft liggen voor degene die het oplost. De meeste experts achten het onwaarschijnlijk dat P=NP. In een recent onderzoek van de University of Maryland onder 100 vooraanstaande wiskundigen en informatici zeggen 9 onderzoekers te geloven in een bewijs, 61 in een bewijs van het tegendeel, en 30 waren niet zeker of gaven geen antwoord.
Desondanks duiken er regelmatig claims op van “bewijzen” dat P=NP. Vaak zijn ze eenvoudig te weerleggen, maar soms ook niet. Een groep Nederlandse, Duitse en Belgische onderzoekers ontkracht in hun paper deze week een mogelijk bewijs dat al uit de jaren ‘80 stamt. ‘In 1986 claimde de Canadese wiskundige Ted Swart dat hij het handelsreizigersprobleem snel kon oplossen met een zogenaamd lineair programma,’ zegt onderzoeker Ronald de Wolf (CWI). ‘Dit zorgde voor grote opwinding in de wiskundige wereld, maar al snel bleek niemand zijn resultaten te kunnen verifiëren. Na ongeveer een jaar bewees Mihalis Yannakakis dat 'symmetrische' lineaire programma’s zoals die van Swart überhaupt niet in staat zijn om het handelsreizigersprobleem snel op te lossen. Maar het idee om lineaire programma’s te gebruiken bleef bestaan. 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.’
Meer informatie:
- S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf. Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds.
- Website Ronald de Wolf (CWI)
Afbeelding: travelingsalesman.org
