denna artikel ursprungligen dök upp på moderkort Tyskland. Sedan dess ursprungliga publikation har den uppdaterats med ny information från moderkort oss. Vad har härdbar cancer, rättvis kapitalism och det perfekta spelet Super Mario Bros. alla gemensamt? Enligt en matematisk teori skulle lösningen på något av dessa problem göra det möjligt för oss att snabbt lösa de andra., Allt som behövs är bättre algoritmer för att bevisa att komplicerade frågor—som proteinvikning, effektiva marknadsplatser och kombinatoriska analyser—bara är variationer av enklare problem som superdatorer redan kan lösa. Men hur kan en algoritm förenkla extremt komplicerade problem? Det beror på en annan fråga: vad händer om komplicerade problem verkligen bara är enkla problem i förklädnad?, Denna gåta är fortfarande en av de största olösta frågorna om modern matematik, och är ett av de sju Millennieprisproblemen, för vilka varje accepterat svar belönas med en miljon dollar.
nu har en tysk man vid namn Norbert Blum påstått sig ha löst ovanstående gåta, som är korrekt känd som p vs NP-problemet. Tyvärr bär hans påstådda lösning inte goda nyheter., Blum, som är från Universitetet i Bonn, hävdar i sitt nyligen publicerade 38-sidiga papper att P inte motsvarar NP. Med andra ord, komplicerade problem är fundamentalt annorlunda än enkla problem och det ser inte ut som våra högpresterande datorer kommer att kunna knäcka dessa svåraste problem när som helst inom en snar framtid. Och i dagarna sedan hans papper publicerades har många matematiker börjat ta upp frågor om huruvida Blum löst det alls.
vad exakt är P versus NP-problemet?,
de flesta Dataforskare tenderar att hålla med Blums slutsats. Svåra problem är svåra, enkla problem är lätta. I datavetenskap faller lätta problem vanligtvis under P. det betyder att de kan lösas i ”polynom”, vilket är mycket som att säga att de kan lösas under en rimlig tidsperiod. Mycket svårare är NP-problemen, vilka datorer inte kan lösa i en rimlig tidsram. För praktiska ändamål kan NP-problem lika gärna vara olösliga av datorer., (Observera dock att NP står för” nondeterministic polynomial time ”snarare än” not polynomial ” tid.) Här är några exempel på NP-problem:
proteinvikning: processen genom vilken proteiner i en biologisk organism erhåller sin struktur. Bättre inblick i denna process kan hjälpa oss att känna igen eller till och med hindra mutationer, vilket kan bota vissa former av cancer. Optimerad routefinding: en optimerad resväg genom 15 olika städer utan att besöka samma stad två gånger?, En hård mutter att spricka, även för en superdator, varför detta också anses vara ett NP-problem inom datavetenskap.
det perfekta schackspelet: ett schackspel har oändliga möjliga drag, så att även en superdator med otrolig kapacitet inte kan bestämma en perfekt taktik. Många matematiker anser att detta problem är så svårt att de inte anser att det är ett NP-problem, utan snarare anser att det är helt ur möjligheten.,
alla dessa komplexa problem har en sak gemensamt: så svårt som det kan vara att hitta en lösning på NP-problem är det relativt lätt att kontrollera giltigheten av lösningarna när du har dem.
dessa två kategoriska skillnader i problemkomplexitet har sitt ursprung före den samhälleliga ökningen av hemdatorer. På 1970-talet, när datorer fortfarande var storleken på ett klumpigt kylskåp, bestämdes det snabbt att inte alla mänsklighetens problem helt enkelt kunde lösas av dessa maskiner., Det föreslogs att skillnaden skulle kunna formaliseras när det gäller beräkningskomplexitet, vilket ledde till en uppsättning komplexitetsklasser, inklusive N och NP.
sedan den formella definitionen av P och NP 1971 har Dataforskare diskuterat huruvida det skulle vara möjligt att komma med en algoritm som kan minska eller omdefiniera NP-problem så att de kan lösas i polynom tid. Om någon skulle kunna bevisa att alla NP-problem i slutändan bara är variationer av P-problem, skulle alla NP-problem i huvudsak vara föremål för samma form av minskning., Med andra ord, den som vet den perfekta Super Mario Bros taktik kan också bota cancer.
totalt har 116 av de modigaste inom sitt område officiellt försökt lösa detta mysterium (även om otaliga fler Dataforskare har lagt upp lösningar på messageboards och på webbplatser som arXiv). Hittills har ingen av dessa bevis officiellt erkänts av matematiksamfundet.
en sorts Vem vill bli miljonär?, för matematiker
år 2000 sammanställde Clay Mathematics Institute (CMI), som ligger i Oxford, en lista över sju olösta Millennieprisproblem och lovade en miljon dollar för varje lösning. Det är en sorts som vill bli miljonär? eller X-priset för matematiker. Millennieprisproblemen anses vara exceptionellt svåra även i expertkretsar. En mängd fältspecifika kunskaper är nödvändiga för att ens förstå frågorna., Det enda Millennieprisproblemet som hittills lösts är Poincaré-gissningen, som inte lätt förklaras som en sida i en artikel om ett annat matematikkoncept.
att lösa NP-problemet skulle inte vara en helt bra sak. Till exempel är de flesta kryptering baserad på svårigheten att factoring mycket stora primtal. Heltal faktorisering är en klass NP problem. En 256-bitars kod, som de som finansiella institutioner använder i online kreditkortsbetalningar, anses okrossbar, och därmed mycket säker., Skulle någon bevisa att NP gör lika P, skulle bankerna snabbt behöva komma med en annan säkerhetsmetod.
vad tycker matematiker om Blums matematiska bevis?
sedan Blums papper publicerades har matematiker och datavetare över hela världen rackat sina hjärnor om huruvida den Bonnbaserade forskaren faktiskt har löst detta Millennieprisproblem. Efter en initialt positiv reaktion, som den från Stanford matematiker Reza Zadeh, börjar tvivel uppstå om huruvida Blums resonemang är korrekt.,
i ett forum för teoretisk matematik nådde en användare som heter Mikhail ut till Alexander Razborov—författaren till det papper som Blums bevis bygger på—för att fråga honom om Blums papper. Razborov påstår sig ha upptäckt ett fel i Blums papper: Blums huvudargument motsäger en av Razborovs viktigaste antaganden. Och matematiker Scott Aaronson, som är något av en auktoritet i mattegemenskapen när det gäller P vs., NP, sa att han skulle vara villig att satsa $200,000 att Blums matematiska bevis inte kommer att uthärda. ”Snälla sluta fråga”, skriver Aaronson. Om bevisen inte har motbevisats, ” du kan komma tillbaka och berätta att jag var en sluten dåre.”I veckan sedan Aaronsons första blogginlägg har andra matematiker börjat försöka peta hål i Blums bevis. Dick Lipton, en datavetenskapsprofessor vid Georgia Tech, skrev i ett blogginlägg att Blums bevis ”passerar många filter av allvar”, men föreslog att det kan finnas några problem med det., En kommentar till det blogginlägget, känt endast som ”vloodin”, noterade att det fanns ett ”enda fel på en subtil punkt” i beviset; andra matematiker har sedan chimed in och bekräftat vloodin inledande analys, och så den framväxande konsensus bland många matematiker är att en lösning för P vs NP förblir svårfångade. Översatt av Melina McCormack.