En matematisk folkesport?

Så fik jeg holdt mit foredrag om NP-fuldstændighed i Ungdommens Naturvidenskabelige Forening. Nogle blandt publikum stod af (jeg glemte, at man ikke må bruge sumtegn og indekserede variabler – den slags kender gymnasieelever ikke), andre tilhørere, der tydeligt havde overstået gymnasietiden, var derimod meget interesserede, og især da i spørgsmålet om P=NP. Ideen om et åbent matematisk problem, der er forholdsvis let at formulere men ikke helt nemt at løse, appellerer til mange lægfolk. Det krævede en del fortolkning fra mig at forstå spørgsmål som: Kan man ikke bare oversætte det til et problem om frekvenser? Kan man ikke bare regne baglæns?

Der er faktisk mange, der har prøvet at bevise at P=NP eller det modsatte. Den østrigske matematiker Gerhard Woeginger, der er professor ved TU Eindhoven, har en fascinerende webside med en fortegnelse over forsøg, han kender til, på at vise at P = NP og på at vise at P ikke er lig NP. Woeginger kender til i alt 94 forsøg, og 47 af dem hævder at vise at P = NP. De fleste af resten hævder at P er forskellig fra NP. Der er masser af bud på polynomielle algoritmer for NP-fuldstændige problemer; dette falder mange lettere end at give sig i kast med at vise det mere kedelige negative resultat. Her kan man finde korte argumenter baseret på Gödels første ufuldstændighedssætning (hvad den stakkels sætning dog ikke bliver udsat for!) og forsøg på at vise at P=NP ikke kan bevises inden for Zermelo-Fraenkel-aksiomerne.

Hvad faktisk alle forsøgene på Woegingers liste har fælles er, at de er gjort af mennesker, der ikke er kendte forskere inden for kompleksitetsteori. Nogle er lægfolk, andre er studerende, atter andre er faktisk akademikere på ikke særligt prestigefyldte institutioner. Nogle bidrag er blevet publiceret – flere endda i tidsskrifter, men igen i tidsskrifter der ikke er særligt velansete. En særligt vedholdende person er Anatoly Plotnikov fra Ukraine. Han har i 1996 og igen i 2007 bevist at P=NP, mens han i 2011 har bevist at P ikke er lig NP. Det må siges at være en helgardering.

Det er påfaldende, at så mange mennesker med forholdsvis begrænset ballast inden for kompleksitetsteori kaster sig over at løse dette meget svære problem. Kunne man forestille sig en motionist fra Nørresundby, der satte sig for at slå verdensrekorden i 400 meter-løb? Jeg tror det næppe.

Et af de få seriøse bud fra de senere år skyldes Vinay Deolalikar, der er en indisk matematiker ansat ved HP Labs. Han forsøgte i 2010 at bruge ideer fra endelig modelteori sammen med statistisk mekanik til at vise at P er forskellig fra NP, men der er i dag konsensus om at heller ikke dette forsøg på et bevis er korrekt. Men Deolalikar havde måske fat i noget rigtigt. Min egen intuition siger mig, at der skal et gennembrud af de større til for at finde ud af om P=NP, og at det vil være led i en ny matematisk teoridannelse af betydning. Grunden til at jeg tror at dette må være tilfældet, er at resultatet (uanset hvad det er) vil have så mange implikationer.

Alene en oversigt over implikationerne af at vise at P=NP eller det modsatte er interessant læsning. En god oversigtsartikel at starte med er Lance Fortnows artikel The Status of the P versus NP Problem  fra Communications of the ACM.