Alright, siden jeg kan, så vil jeg gerne lige forsøge at give de interesserede lidt perspektiv på den Der er en der har bevist at P er forskellig fra NP-historie, der flyder rundt på nettet for tiden.
P og NP er navnene på to klasser af opgaver man kan bede en computer regne på. Hvis vi skal springe alt det svære over, men dog forklare lidt, så er P den slags opgaver det er let at regne på, altså hvor maskinen faktisk bliver færdig før universet er gået under.
NP er defineret ved hjælp af P - det er alle de opgaver, hvor det er let at tjekke om man har fundet en løsning. Man må selv om hvordan man finder den, man kan søge efter den på en eller anden måde, men når man har en mulig løsning, så skal prisen være lav på at tjekke løsningen.
Intuitionen hos matematikere har, som man næsten kan forstå bare af ovenstående, været at NP er en meget større klasse end P. Det lyder for godt til at være sandt, at man helt gratis kan få søgninger i kæmpestore rum af mulige løsninger forærerende, hvis man bare sikrer sig at det er let at tjekke løsningerne.
Tag bare matematikfaget selv. Det man gør som matematiker er med stort møje og besvær at navigere rundt i begreberne og finde en sikker vej fra nogle forudsætninger man ved passede i forvejen til noget nyt, man ikke vidste om var sandt. Så skriver man ruten ned fra det man vidste før, hen til det nye, som man nu har fundet ud af. Den rute er det vi normalt kalder et matematisk bevis. Det er lige præcis en forklaring, som det er nemt at tjekke, på hvordan man kommer fra et kendt sted til et ukendt sted. Hvis NP bare var P i forklædning, så kunne man springe alle vanskelighederne over. Så kunne man i princippet bare lade maskiner udvikle al matematikken, selv finde vej i det vanskelige landskab.
Af den grund - og af flere andre - har opfattelsen været siden spørgsmålet blev stillet, at de to klasser af opgaver måtte være forskellige.
Men, spørgsmålet om P = NP blev formuleret for omkring 40 år siden, og siden da er det stort set ingen fremskridt sket i retning af at finde en løsning. Tværtimod. Gennem tiderne har man fundet nogle mærkværdige og ret gennemgribende forhindringer for at finde et svar på om P = NP eller ej.
Da Clay Matematikinstituttet lavede en liste over de syv vigtigste uløste problemer i matematik, og udlovede en dusør på en million dollars for løsningen på hvert af dem, kom P vs NP med på listen. Min fornemmelse, selvom jeg forlod faget for en del år siden, er at mange matematikere nok egentlig synes at P vs NP er letvægteren på listen af de syv problemer. For det første er det computervidenskab og ikke ren matematik.
For det andet, så er formodningen om hvad det rigtige svar er så ensidig, at det måske ikke rigtig talte som en gåde. Ikke alene regner næsten alle med at P og NP er forskellige, men vi har alle lænet os op af den antagelse i årevis. Blandt andet er snart sagt al kryptering og sikkerhed på nettet baseret på P og NP er forskellige. Hvis ikke det var rigtigt, så kunne man i teorien læse stort set alle krypterede meddelelser.
Ikke desto mindre, så er der en kæmpe dusør for den rigtige løsning, og problemet er berømt. I matematikverdenen betyder den slags, at tusindevis af mere eller mindre begavede amatører begynder at skrive breve til de profesionelle, med mere eller mindre mystiske "beviser" på påstanden.
Matematik har altid haft en stærk tiltrækningskraft på crackpots. De mystiske tegn og gerninger er bare for spændende til at lade ligge, og de berømte uløste gåder har fået i titusindevis af fejlagtige løsninger gennem tiderne.
Det meste berømte af de uløste problemer, Fermats Sidste Sætning, var så stor en tossemagnet at en berømt professer i talteori fik udfærdiget fortrykte brevkort til svar. På kortet sted teksten
Kære __________Tak for Deres henvendelse, med et bevis af Fermats Sidste Sætning.
Den første fejl i deres bevis står på side ______.
Venlig Hilsen
Han gav så sine specialestuderende de dårlige beviser og en stak postkort til udfyldning, som opgaver.
Det er på den baggrund man skal forstå det der sker nu, nemlig at de professionelle matematikere er overordentlig meget i tvivl om det nu også virkelig kan passe at det nye bevis holder vand. Der har simpelthen været for mange dårlige beviser, til at man uden videre tager endnu et bevis alvorligt, der i sagens natur bruger nye eksotiske teknikker - de gamle har jo ikke leveret en løsning.
En enkelt, Scott Aronson, er endda gået så vidt, at han har lovet, af egen lomme, at lægge tohundredetusinde dollars til Clay dusøren, hvis beviset viser sig at holde vand.
Det nye ved det nye bevis, er at det er skrevet af en fagmand. Godt nok ikke en, der primært laver kompleksitetsteori - som feltet hedder, men dog en velmeriteret fagmand, og så er der mindre grund til at tro at han er gået på grund undervejs - men juryen er altså stadigvæk i den grad ude.
Posted by Claus at August 10, 2010 10:28 AM | TrackBack (0)