Hva betyr 'P vs. NP' for resten av oss?

Programmerere og informatikere har surret den siste uken om det siste forsøket på å løse et av de mest irriterende spørsmålene innen informatikk: det såkalte P versus NP-problemet.





Vinay Deolalikar, en forsker ved HP Labs i Palo Alto, CA, la ut beviset sitt på nettet og sendte det til flere eksperter på området 6. august. Kolleger begynte umiddelbart å dissekere beviset på akademiske blogger og wikier. Tidlige reaksjoner var respektfulle, men skeptiske, og den nåværende konsensus er at Deolalikars tilnærming er fundamentalt feil.

Et solid bevis ville gi Deolalikar berømmelse og formue. De Clay Mathematics Institute i Cambridge, MA, har kalt P versus NP som et av sine Millennium-problemer, og tilbyr $1 million til alle som gir et verifisert bevis.

Men P versus NP er mer enn bare et abstrakt matematisk puslespill. Den søker å bestemme – en gang for alle – hvilke typer problemer som kan løses av datamaskiner, og hvilke som ikke kan. P-klasse problemer er enkle å løse for datamaskiner; det vil si at løsninger på disse problemene kan beregnes på rimelig tid sammenlignet med kompleksiteten til problemet. I mellomtiden, for NP-problemer, kan en løsning være veldig vanskelig å finne – kanskje krever beregninger for milliarder av år – men når den først er funnet, kan den enkelt sjekkes. (Se for deg et puslespill: det er vanskelig å finne riktig arrangement av brikker, men du kan se når puslespillet er ferdig ferdig bare ved å se på det.)



NP-klasseproblemer inkluderer mange mønstertilpasnings- og optimaliseringsproblemer som er av stor praktisk interesse, for eksempel å bestemme det optimale arrangementet av transistorer på en silisiumbrikke, utvikle nøyaktige økonomiske prognosemodeller eller analysere proteinfoldingsadferd i en celle.

P versus NP-problemet spør om disse to klassene faktisk er identiske; det vil si om hvert NP-problem også er et P-problem. Hvis P er lik NP, vil hvert NP-problem inneholde en skjult snarvei, slik at datamaskiner raskt kan finne perfekte løsninger på dem. Men hvis P ikke er lik NP, eksisterer ingen slike snarveier, og datamaskiners problemløsningsevne vil forbli fundamentalt og permanent begrenset. Praktisk erfaring tyder i overveiende grad på at P ikke er lik NP. Men inntil noen gir et solid matematisk bevis, forblir gyldigheten av antagelsen åpen for spørsmål.

Selv om Deolalikars bevis ble funnet å være forsvarlig, gjenstår spørsmålet – hvilken innvirkning ville et slikt bevis ha på relevante områder av databehandling?



Overfladisk sett kan man kanskje tro at svaret ikke er mye. Å bevise at P ikke er lik NP ville bare bekrefte det nesten alle allerede antar er sant for praktiske formål, forklarer Scott Aaronson , en kompleksitetsforsker ved MITs Computer Science and Artificial Intelligence Laboratory.

For eksempel danner vår manglende evne til å effektivt faktorisere enorme sammensatte tall (et klassisk NP-problem) grunnlaget for moderne kryptografi – som underbygger alt fra nasjonal sikkerhet til Amazon.com-kjøp. Vi trenger ikke et formelt bevis på at P ikke er lik NP for å stole på formodningen, sier Aaronson. Programmerere vet om problemet og ville vært glade for å se at P ikke er lik NP bevist, men på et daglig nivå vet de at det å omformulere [et NP-problem] til noe enklere gir mye mer mening enn å prøve å løse det matematiske århundres problem.

Fordi problemer i NP-klassen er så gjennomgripende (selv sudoku-oppgaver og søk på flyselskaper på Bing.com er beregningsmessig vanskelig), oppdages det stadig nye løsninger. Stokastisk optimalisering, for eksempel, etterligner tilfeldigheten som finnes i fysiske systemer (som avkjøling av metaller eller muterende DNA) for å produsere gode nok løsninger i stedet for beregningsmessig harde.



Forsøk på å takle antakelsen om at P ikke er lik NP hjelper oss med å utvikle nye mentale teknologier, sier Richard Lipton , en informatiker ved Georgia Tech som studerer P versus NP-problemet. Selv om vi har skrevet algoritmer i flere tiår, forstår vi ikke helt hva de er i stand til, fortsetter han. Så selv om du beviste at P ikke er lik NP – noe alle allerede tror – ville det måtte utvide forståelsen vår av disse egenskapene radikalt, og gjøre mange nye ting mulig med datamaskiner, i tillegg til alle de smarte løsningene vi allerede har funnet.

Så hvis inkrementell fremgang fortsatt kan generere nyttig innovasjon, hvorfor er ikke titaner av industriell forskning som Google, Microsoft og HP (som alle nektet å kommentere for denne artikkelen) som vier store team av forskere til P ikke det samme som NP-puslespill? Å bevise en negativ er bare utrolig vanskelig, og fra [et stort selskaps] synspunkt har det sannsynligvis ikke stor innvirkning på det neste finanskvartalet eller til og med de neste årene av virksomheten deres, sier Lipton. Det er mer et langsiktig problem.

Selvfølgelig er det alltid alternativet: å bevise at P gjør faktisk lik NP. Men ikke hold pusten, sier Aaronson. Det er gode grunner til at de færreste tror at P er lik NP, sier han. Hvis det gjorde det, ville vi levd i et fundamentalt annet univers, og vi ville sannsynligvis ha lagt merke til det nå.



gjemme seg