211service.com
Hvad betyder 'P vs. NP' for os andre?
Programmører og dataloger har i den seneste uge summet om det seneste forsøg på at løse et af de mest irriterende spørgsmål inden for datalogi: det såkaldte P versus NP-problem.
Vinay Deolalikar, en forsker ved HP Labs i Palo Alto, Californien, lagde sit bevis online og sendte det til flere eksperter på området den 6. august. Kolleger begyndte straks at dissekere beviset på akademiske blogs og wikier. De tidlige reaktioner var respektfulde, men skeptiske, og den nuværende konsensus er, at Deolalikars tilgang er fundamentalt mangelfuld.
Et solidt bevis ville give Deolalikar berømmelse og formue. Det Clay Mathematics Institute i Cambridge, MA, har navngivet P versus NP som et af dets Millennium-problemer og tilbyder 1 million dollars til enhver, der giver et verificeret bevis.
Men P versus NP er mere end blot et abstrakt matematisk puslespil. Den søger at afgøre – én gang for alle – hvilke slags problemer der kan løses af computere, og hvilke der ikke kan. P-klasse problemer er nemme at løse for computere; det vil sige, at løsninger på disse problemer kan beregnes inden for en rimelig tid i forhold til problemets kompleksitet. I mellemtiden, for NP-problemer, kan en løsning være meget svær at finde - måske kræver det milliarder af års beregning - men når den først er fundet, er den let at kontrollere. (Forestil dig et puslespil: Det er svært at finde det rigtige arrangement af brikker, men du kan se, hvornår puslespillet er færdigt korrekt, bare ved at se på det.)
NP-klassens problemer omfatter mange mønstertilpasnings- og optimeringsproblemer, der er af stor praktisk interesse, såsom at bestemme det optimale arrangement af transistorer på en siliciumchip, udvikle nøjagtige økonomiske prognosemodeller eller analysere proteinfoldningsadfærd i en celle.
P versus NP-problemet spørger, om disse to klasser faktisk er identiske; det vil sige om ethvert NP-problem også er et P-problem. Hvis P er lig med NP, vil hvert NP-problem indeholde en skjult genvej, som gør det muligt for computere hurtigt at finde perfekte løsninger på dem. Men hvis P ikke er lig med NP, så eksisterer der ikke sådanne genveje, og computeres problemløsningsevne vil forblive fundamentalt og permanent begrænset. Praktisk erfaring tyder i overvejende grad på, at P ikke er lig med NP. Men indtil nogen giver et solidt matematisk bevis, er gyldigheden af antagelsen åben for spørgsmål.
Selv hvis Deolalikars bevis blev fundet at være forsvarligt, så er spørgsmålet tilbage – hvilken indflydelse ville et sådant bevis have på relevante områder inden for computing?
Overfladisk kan man tro, at svaret ikke er meget. At bevise, at P ikke er lig med NP, ville blot bekræfte, hvad næsten alle allerede antager for at være sandt af praktiske formål, forklarer Scott Aaronson , en kompleksitetsforsker ved MIT's Computer Science and Artificial Intelligence Laboratory.
For eksempel danner vores manglende evne til effektivt at faktorisere enorme sammensatte tal (et klassisk NP-problem) grundlaget for moderne kryptografi – som understøtter alt fra national sikkerhed til Amazon.com-køb. Vi behøver ikke et formelt bevis for, at P ikke er lig med NP for at stole på formodningen, siger Aaronson. Programmører kender til problemet og ville være glade for at se, at P ikke er lig med NP bevist, men på et dagligt niveau ved de, at det giver meget mere mening at omformulere [et NP-problem] til noget lettere end at prøve at løse det matematiske. århundredes problem.
Fordi problemer i NP-klassen er så udbredte (selv sudoku-puslespil og flyselskabs-plansøgninger på Bing.com er beregningsmæssigt svære), bliver innovative løsninger konstant opdaget. Stokastisk optimering efterligner for eksempel den tilfældighed, der findes i fysiske systemer (såsom kølende metaller eller muterende DNA) for at producere gode nok løsninger i stedet for beregningshårde.
Forsøg på at klare antagelsen om, at P ikke er lig med NP, hjælper os med at udvikle nye mentale teknologier, siger Richard Lipton , en datalog ved Georgia Tech, der studerer P versus NP-problemet. Selvom vi har skrevet algoritmer i årtier, forstår vi ikke helt, hvad de er i stand til, fortsætter han. Så selvom du beviste, at P ikke er lig med NP – noget som alle allerede tror – ville det være nødt til radikalt at udvide vores forståelse af disse muligheder og gøre mange nye ting mulige med computere, ud over alle de smarte løsninger, vi allerede har fundet.
Så hvis trinvise fremskridt stadig kan generere nyttig innovation, hvorfor er titaner af industriel forskning som Google, Microsoft og HP (som alle afviste at kommentere til denne artikel) ikke at afsætte store teams af forskere til P ikke lig med NP-puslespil? At bevise et negativt er bare utroligt svært, og fra [en stor virksomheds] synspunkt har det sandsynligvis ikke meget indflydelse på det næste finansielle kvartal eller endda de næste par år af deres forretning, siger Lipton. Det er mere et langsigtet problem.
Selvfølgelig er der altid alternativet: at bevise, at P gør faktisk lig NP. Men hold ikke vejret, siger Aaronson. Der er gode grunde til, at de færreste tror, at P er lig med NP, siger han. Hvis det gjorde det, ville vi leve i et fundamentalt andet univers, og det ville vi nok have bemærket nu.