Dit artikel verscheen oorspronkelijk op Motherboard Germany. Sinds de oorspronkelijke publicatie is het bijgewerkt met nieuwe informatie door Motherboard US. Wat hebben geneesbare kanker, eerlijk kapitalisme en het perfecte spel van Super Mario Bros. met elkaar gemeen? Volgens een wiskundige theorie, zou de oplossing voor een van deze problemen ons in staat stellen om snel de andere op te lossen., Het enige dat nodig is, zijn betere algoritmen om te bewijzen dat ingewikkelde vragen—zoals eiwitvouwen, efficiënte marktplaatsen en combinatorische analyses—slechts variaties zijn van eenvoudigere problemen die supercomputers al kunnen oplossen. Maar hoe kan één algoritme extreem ingewikkelde problemen vereenvoudigen? Dat hangt af van een andere vraag: Wat als ingewikkelde problemen eigenlijk gewoon eenvoudige vermomde problemen zijn?, Dit raadsel blijft een van de grootste onopgeloste vragen van de moderne wiskunde, en is een van de zeven Millennium Prijs problemen, waarvoor elk geaccepteerd antwoord wordt beloond met een miljoen dollar.
nu heeft een Duitser, Norbert Blum, beweerd het bovenstaande raadsel te hebben opgelost, dat goed bekend staat als het P vs NP-probleem. Helaas, zijn vermeende oplossing draagt geen goed nieuws., Blum, van de Universiteit van Bonn, beweert in zijn onlangs verschenen 38 pagina ‘ s tellende paper dat P niet gelijk staat aan NP. Met andere woorden, ingewikkelde problemen zijn fundamenteel anders dan eenvoudige problemen en het lijkt er niet op dat onze high-performance computers in staat zullen zijn om deze moeilijkste problemen op elk moment in de nabije toekomst te kraken. En in de dagen sinds zijn paper werd gepubliceerd, zijn tal van wiskundigen begonnen vragen te stellen over de vraag of Blum het überhaupt heeft opgelost.
Wat is precies het P versus NP probleem?,
De meeste computerwetenschappers zijn het eens met de conclusie van Blum. Moeilijke problemen zijn moeilijk, gemakkelijke problemen zijn gemakkelijk. In de informatica vallen eenvoudige problemen meestal onder de vaandel van P. dit betekent dat ze kunnen worden opgelost in “polynomiale tijd”, wat veel lijkt op zeggen dat ze kunnen worden opgelost in een redelijke periode van tijd. Veel moeilijker zijn de NP problemen, die computers niet in staat zijn om op te lossen in een redelijke tijd. Voor praktische doeleinden kunnen NP-problemen net zo goed onoplosbaar zijn door computers., (Merk echter op dat NP staat voor “niet-deterministische polynomiale tijd” in plaats van “niet-polynomiale” tijd.) Hier zijn enkele voorbeelden van NP problemen:
eiwit folding: het proces waardoor eiwitten in een biologisch organisme hun structuur verkrijgen. Een beter inzicht in dit proces kan ons helpen mutaties te herkennen of zelfs belemmeren, die bepaalde vormen van kanker kunnen genezen. Geoptimaliseerde routefinding: een geoptimaliseerde reisroute door 15 verschillende steden zonder twee keer dezelfde stad te bezoeken?, Een harde noot om te kraken, zelfs voor een supercomputer, daarom wordt dit ook beschouwd als een NP-probleem in de informatica.
het perfecte schaakspel: een schaakspel heeft oneindig veel mogelijke zetten, zodat zelfs een supercomputer met ongelooflijke capaciteit geen perfecte tactiek kan bepalen. Veel wiskundigen vinden dit probleem zo moeilijk dat ze het niet als een NP-probleem beschouwen, maar het volledig buiten het bereik van de mogelijkheden houden.,
al deze complexe problemen hebben één ding gemeen: hoe moeilijk het ook is om een oplossing te vinden voor NP-problemen, het is relatief eenvoudig om de geldigheid van de oplossingen te controleren als je ze eenmaal hebt.
Deze twee categorische verschillen in probleemcomplexiteit hebben hun oorsprong vóór de maatschappelijke opkomst van thuiscomputers. In de jaren zeventig, toen computers nog zo groot waren als een onhandige koelkast, werd al snel vastgesteld dat niet alle problemen van de mensheid eenvoudig konden worden opgelost door deze machines., Er werd voorgesteld dat het onderscheid geformaliseerd kon worden in termen van computationele complexiteit, wat leidde tot een reeks complexiteitsklassen, waaronder N en NP.sinds de formele definitie van P en NP in 1971 hebben computerwetenschappers gedebatteerd over de vraag of het mogelijk zou zijn om een algoritme te ontwikkelen dat NP-problemen kan verminderen of herdefiniëren, zodat ze in polynomiale tijd kunnen worden opgelost. Zou iemand kunnen bewijzen dat alle NP-problemen uiteindelijk slechts variaties van P-problemen zijn, dan zouden alle NP-problemen in wezen onderworpen zijn aan dezelfde vorm van reductie., Met andere woorden, wie de perfecte Super Mario Bros.tactiek kent, kan ook kanker genezen.
in totaal hebben 116 van de dappersten in hun vakgebied officieel geprobeerd dit mysterie op te lossen (hoewel er nog veel meer computerwetenschappers mogelijke oplossingen hebben gepost op messageboards en op sites als arXiv). Tot op heden is geen van deze bewijzen officieel erkend door de wiskundige gemeenschap.
een soort die miljonair wil worden?, voor wiskundigen
in 2000 stelde het Clay Mathematics Institute (CMI), gevestigd in Oxford, een lijst samen van zeven onopgeloste Millennium Prijs problemen, waarbij een miljoen dollar werd toegezegd voor elke oplossing. Het is iemand die miljonair wil worden? of X prijs voor wiskundigen. De Millenniumprijsproblemen worden zelfs in deskundige kringen als buitengewoon moeilijk beschouwd. Een schat aan veldspecifieke kennis is nodig om zelfs de vragen te begrijpen., Het enige probleem van de Millenniumprijs dat tot nu toe is opgelost, is het vermoeden van Poincaré, dat niet gemakkelijk kan worden uitgelegd als een terzijde in een artikel over een ander wiskundeconcept.
het oplossen van het NP-probleem zou niet helemaal goed zijn. Bijvoorbeeld, de meeste encryptie is gebaseerd op de moeilijkheid van factoring zeer grote priemgetallen. Integer factorisatie is een klasse NP probleem. Een 256-bit code, zoals die welke financiële instellingen gebruiken in online creditcardbetalingen, wordt beschouwd als onbreekbaar en dus zeer veilig., Als iemand zou bewijzen dat NP gelijk is aan P, zouden banken snel met een andere beveiligingsmethode moeten komen.
Wat vinden wiskundigen van Blum ‘ s wiskundige bewijs?sinds Blum ‘ s paper werd gepubliceerd, hebben wiskundigen en computerwetenschappers over de hele wereld zich afgevraagd of de onderzoeker uit Bonn dit Millenniumprijsprobleem wel heeft opgelost. Na een aanvankelijk positieve reactie, zoals die van Stanford wiskundige Reza Zadeh, beginnen twijfels te ontstaan over de vraag of Blum ‘ s redenering juist is.,
In een forum voor theoretische wiskunde zocht een gebruiker genaamd Mikhail contact met Alexander Razborov—de auteur van het artikel waarop Blum ’s bewijs is gebaseerd—om hem naar Blum’ s artikel te vragen. Razborov beweert een fout te hebben ontdekt in Blum ’s paper: Blum’ s belangrijkste argument is in tegenspraak met een van Razborov ‘ s belangrijkste veronderstellingen. En wiskundige Scott Aaronson, die een autoriteit is in de wiskunde gemeenschap als het gaat om P vs., NP, zei dat hij bereid zou zijn om $200.000 te wedden dat Blum ‘ s wiskundige bewijs niet zal doorstaan. “Hou op met vragen,” schrijft Aaronson. Als het bewijs niet is weerlegd ,” je kunt terugkomen en me vertellen dat ik een bekrompen dwaas was.”In de week sinds Aaronson’ s eerste blog post, andere wiskundigen zijn begonnen te proberen gaten in Blum ‘ s bewijs. Dick Lipton, een computer science professor aan Georgia Tech, schreef in een blog post dat Blum ‘ s bewijs “passeert vele filters van ernst,” maar suggereerde dat er misschien een aantal problemen met het., Een commentator op die blogpost, alleen bekend als “vloodin”, merkte op dat er een “enkele fout op een subtiel punt” in het bewijs was; andere wiskundigen hebben sindsdien ingegrepen en bevestigd vloodin ‘ s initiële analyse, en dus de opkomende consensus onder veel wiskundigen is dat een oplossing voor P vs.NP ongrijpbaar blijft. Vertaald door Melina McCormack.