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. De meeste experts achten het onwaarschijnlijk dat P=NP. Desondanks duiken er regelmatig claims op van “bewijzen” dat P=NP. Vaak zijn ze eenvoudig te weerleggen, maar soms ook niet. Een groep onderzoekers ontkracht in hun paper een mogelijk bewijs dat al uit de jaren ‘80 stamt. ‘In 1986 claimde de wiskundige Ted Swart dat hij het handelsreizigersprobleem 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. 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 de onderzoekers 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.’
Wetenschappelijke publicatie:
S. Fiorini, S. Massar, S. ***, H.R. Tiwary en R. de Wolf: Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds.
