Springen naar inhoud

- - - - -

Decennia oud 'bewijs' voor P=NP eindelijk weerlegd


  • Log in om te kunnen reageren

#1

Wien Ee

    Wien Ee


  • >1k berichten
  • 3133 berichten
  • VIP

Geplaatst op 27 mei 2012 - 10:14

Het handelsreizigersprobleem is nog altijd niet opgelost. Een 26 jaar oude claim voor de oplossing van het probleem is eindelijk definitief ontkracht.

Geplaatste afbeelding

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. Pokutta, H.R. Tiwary en R. de Wolf: Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds.
Heb je interesse in journalistiek? Wij zoeken versterking! Speurwerk, deel van het team, meer weten: klik.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.




0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures