211service.com
Wat betekent 'P vs. NP' voor de rest van ons?
Programmeurs en computerwetenschappers hebben de afgelopen week geroeid over de laatste poging om een van de meest irritante vragen in de informatica op te lossen: het zogenaamde P versus NP-probleem.
Vinay Deolalikar, een onderzoekswetenschapper bij HP Labs in Palo Alto, CA, plaatste zijn bewijs online en stuurde het op 6 augustus naar verschillende experts in het veld. Collega's begonnen onmiddellijk het bewijs te ontleden op academische blogs en wiki's. De eerste reacties waren respectvol maar sceptisch, en de huidige consensus is dat de benadering van Deolalikar fundamenteel gebrekkig is.
Een solide bewijs zou Deolalikar roem en fortuin opleveren. De Clay Mathematics Institute in Cambridge, MA, heeft P versus NP genoemd als een van zijn millenniumproblemen en biedt $ 1 miljoen aan iedereen die een geverifieerd bewijs levert.
Maar P versus NP is meer dan alleen een abstracte wiskundige puzzel. Het probeert voor eens en voor altijd vast te stellen welke soorten problemen door computers kunnen worden opgelost en welke niet. P-klasse problemen zijn eenvoudig op te lossen door computers; dat wil zeggen dat oplossingen voor deze problemen binnen een redelijke tijd kunnen worden berekend in vergelijking met de complexiteit van het probleem. Ondertussen is een oplossing voor NP-problemen misschien heel moeilijk te vinden - misschien kost het miljarden jaren aan berekeningen - maar eenmaal gevonden, is het gemakkelijk te controleren. (Stel je een legpuzzel voor: het vinden van de juiste volgorde van de stukjes is moeilijk, maar je kunt zien wanneer de puzzel correct is voltooid door ernaar te kijken.)
NP-klasse problemen omvatten veel patroon-matching en optimalisatieproblemen die van groot praktisch belang zijn, zoals het bepalen van de optimale opstelling van transistors op een siliciumchip, het ontwikkelen van nauwkeurige financiële prognosemodellen of het analyseren van eiwitvouwgedrag in een cel.
Het P versus NP-probleem vraagt of deze twee klassen eigenlijk identiek zijn; dat wil zeggen, of elk NP-probleem ook een P-probleem is. Als P gelijk is aan NP, zou elk NP-probleem een verborgen snelkoppeling bevatten, waardoor computers er snel perfecte oplossingen voor kunnen vinden. Maar als P niet gelijk is aan NP, dan bestaan dergelijke snelkoppelingen niet en blijft het probleemoplossende vermogen van computers fundamenteel en permanent beperkt. Praktische ervaring suggereert overweldigend dat P niet gelijk is aan NP. Maar totdat iemand een degelijk wiskundig bewijs levert, blijft de geldigheid van de veronderstelling twijfelachtig.
Zelfs als het bewijs van Deolalikar deugdelijk zou zijn, blijft de vraag: welke impact zou zo'n bewijs hebben op relevante computergebieden?
Oppervlakkig gezien zou je kunnen denken dat het antwoord niet veel is. Bewijzen dat P niet gelijk is aan NP zou alleen maar bevestigen wat bijna iedereen al aanneemt om waar te zijn voor praktische doeleinden, legt uit Scott Aaronson , een complexiteitsonderzoeker bij MIT's Computer Science and Artificial Intelligence Laboratory.
Ons onvermogen om enorme samengestelde getallen efficiënt te factoriseren (een klassiek NP-probleem) vormt bijvoorbeeld de basis van moderne cryptografie, die alles ondersteunt, van nationale veiligheid tot Amazon.com-aankopen. We hebben geen formeel bewijs nodig dat P niet gelijk is aan NP om op het vermoeden te kunnen vertrouwen, zegt Aaronson. Programmeurs kennen het probleem en zouden enthousiast zijn om te zien dat P niet gelijk is aan bewezen NP, maar op een dagelijks niveau weten ze dat het herformuleren van [een NP-probleem] in iets eenvoudigers veel logischer is dan het proberen op te lossen van de wiskundige probleem van de eeuw.
Omdat problemen met de NP-klasse zo alomtegenwoordig zijn (zelfs sudoku-puzzels en zoekopdrachten naar vluchtschema's op Bing.com zijn rekenkundig moeilijk), worden er voortdurend innovatieve oplossingen ontdekt. Stochastische optimalisatie bootst bijvoorbeeld de willekeur na die wordt aangetroffen in fysieke systemen (zoals koelmetalen of muterend DNA) om oplossingen te produceren die goed genoeg zijn in plaats van rekenkundig moeilijke.
Pogingen om om te gaan met de veronderstelling dat P niet gelijk is aan NP, helpen ons nieuwe mentale technologieën te ontwikkelen, zegt: Richard Lipton , een computerwetenschapper bij Georgia Tech die het P versus NP-probleem bestudeert. Ook al schrijven we al tientallen jaren algoritmen, we begrijpen niet helemaal waartoe ze in staat zijn, vervolgt hij. Dus zelfs als je zou bewijzen dat P niet gelijk is aan NP - iets dat iedereen al gelooft - zou het ons begrip van die mogelijkheden radicaal moeten uitbreiden en veel nieuwe dingen mogelijk moeten maken met computers, naast alle slimme oplossingen die we al hebben gevonden.
Dus als stapsgewijze vooruitgang nog steeds nuttige innovatie kan opleveren, waarom zijn titanen van industrieel onderzoek zoals Google, Microsoft en HP (die allemaal weigerden commentaar te geven op dit artikel) die enorme teams van onderzoekers wijden aan de P is niet gelijk aan NP-puzzel? Het bewijzen van een negatief is gewoon ongelooflijk moeilijk, en vanuit het oogpunt van [een groot bedrijf] heeft het waarschijnlijk niet veel invloed op het volgende financiële kwartaal of zelfs de komende jaren van hun bedrijf, zegt Lipton. Het is meer een kwestie van lange adem.
Natuurlijk is er altijd het alternatief: bewijzen dat P doet in feite gelijk NP. Maar houd je adem niet in, zegt Aaronson. Er zijn goede redenen waarom maar heel weinig mensen geloven dat P gelijk is aan NP, zegt hij. Als dat zo was, zouden we in een fundamenteel ander universum leven, en dat hadden we nu waarschijnlijk gemerkt.