fredag 12 juli 2013

P=NP? En miljon dollar för matematiskt genombrott?

Inom datavetenskapen var länge problemet P=NP? svårt att lösa, så svårt att Clay institutet i matematik instiftade ett pris på en miljon dollar för den som löser det. Prispengar har tidigare gett resultat: år 2003 löste den ryske matematiken Grigori Perelman Poincarés förmodan, fast Perelman ville inte ha priset.

Den 6 augusti 2010 lämnade Vinay Deolalikar på HP Labs in en lösning. Effekterna av lösningen skulle då främst kunna ses inom optimeringsläran.

Det är rätt svårt att avgöra om något stämmer eller inte inom matematiken. Så, stämmer lösningen? Scott Aaronson vid MIT har satt ihop en intressant lista på tio punkter att hålla utkik efter för att avgöra om ett matematiskt genombrott inte är sant. Stämmer punkterna in? För Aaronson så var inte Deolalikars lösning korrekt, även Moshe Vardi vid Rice university fann fel och Deolalikar släppte inte information om sin lösning.

Intressant nog kan arbetet med att förkasta Deolalikars lösning ha fört matematiken framåt. Matematikerna kommunicerade via bloggar, wiki och forum, då var det lättare att hitta rätt person i den mycket specialiserade matematiska världen. Det kollektiva samarbetet kring problemet var något nytt, tidigare gick matematisk korrespondens mycket långsammare via e-mail och var ju bara kommunikation i rätt små grupper av matematiker. Sajter som Mathoverflow har sparat in på antalet fysiska seminarier som behövs för att lösa ett problem.

P=NP? är inte bara ett stort hjärnbryderi men det är ett matematiskt problem som också skulle få omedelbar praktisk betydelse, särskilt när det gäller kryptering av datakommunikation. Om informationsproblemet stämmer, och P är lika med NP, skulle få enorma effekter på vår uppfattning av världen.

Den omvälvningen har varit skälet till att många matematiker, som Aaronson, varit skeptiska mot att den lösningen finns. Då skulle det inte finnas någon skillnad mellan att lösa ett problem och att förstå dess lösning, utan ett kreativt språng. Tyvärr så stämmer inte det med hur informationsbehandling ser ut i verkligheten, om du förstår en symfoni så kan du fortfarande inte skriva musik som Beethoven och även om Albert Einstein förklarar fysik för dig steg för steg så kommer du ha svårt att komma på relativitetsteorin.

P=NP? verkar fortsätta att gäcka matematikerna som ett av de stora "olösbara" problemen, vilket nog är dess stora tjusning.

Läs även andra bloggares åsikter om , , , , , ,

Intressant

Universalism mot brutalism

Det görs mycket sökande efter mening i dessa dagar då liberalkonservatismen spelat ut sin roll. Ibland så förs tanken om den stora state...