211service.com
Vad betyder 'P vs. NP' för resten av oss?
Programmerare och datavetare har surrat den senaste veckan om det senaste försöket att lösa en av de mest irriterande frågorna inom datavetenskap: det så kallade P kontra NP-problemet.
Vinay Deolalikar, en forskare vid HP Labs i Palo Alto, CA, lade ut sitt bevis online och skickade det till flera experter på området den 6 augusti. Kollegor började omedelbart dissekera beviset på akademiska bloggar och wikis. Tidiga reaktioner var respektfulla men skeptiska, och den nuvarande konsensusen är att Deolalikars tillvägagångssätt är fundamentalt felaktigt.
Ett solidt bevis skulle tjäna Deolalikar berömmelse och förmögenhet. De Clay Mathematics Institute i Cambridge, MA, har utnämnt P kontra NP som ett av dess Millennium-problem och erbjuder 1 miljon dollar till alla som ger ett verifierat bevis.
Men P kontra NP är mer än bara ett abstrakt matematiskt pussel. Den försöker avgöra – en gång för alla – vilka typer av problem som kan lösas av datorer, och vilka som inte kan. P-klassproblem är lätta för datorer att lösa; det vill säga lösningar på dessa problem kan beräknas på en rimlig tid jämfört med problemets komplexitet. Under tiden, för NP-problem, kan en lösning vara mycket svår att hitta - kanske kräver miljarder års beräkning - men när den väl hittats är den lätt att kontrollera. (Föreställ dig ett pussel: att hitta rätt arrangemang av bitar är svårt, men du kan se när pusslet är korrekt färdigt bara genom att titta på det.)
NP-klassproblem inkluderar många mönstermatchnings- och optimeringsproblem som är av stort praktiskt intresse, som att bestämma det optimala arrangemanget av transistorer på ett kiselchip, utveckla noggranna ekonomiska prognosmodeller eller analysera proteinveckningsbeteende i en cell.
P kontra NP-problemet frågar om dessa två klasser faktiskt är identiska; det vill säga om varje NP-problem också är ett P-problem. Om P är lika med NP, skulle varje NP-problem innehålla en dold genväg, vilket gör att datorer snabbt kan hitta perfekta lösningar på dem. Men om P inte är lika med NP, finns inga sådana genvägar, och datorernas problemlösningsförmåga kommer att förbli fundamentalt och permanent begränsad. Praktisk erfarenhet tyder överväldigande på att P inte är lika med NP. Men tills någon ger ett korrekt matematiskt bevis, förblir giltigheten av antagandet öppen att ifrågasätta.
Även om Deolalikars bevis befanns vara bra, så kvarstår frågan - vilken inverkan skulle ett sådant bevis ha på relevanta datorområden?
Ytligt sett kan man tycka att svaret inte är mycket. Att bevisa att P inte är lika med NP skulle bara bekräfta vad nästan alla redan antar är sant i praktiska syften, förklarar Scott Aaronson , en komplexitetsforskare vid MIT:s datavetenskap och artificiell intelligens Laboratory.
Till exempel, vår oförmåga att effektivt faktorisera enorma sammansatta siffror (ett klassiskt NP-problem) utgör grunden för modern kryptografi – som ligger till grund för allt från nationell säkerhet till Amazon.com-köp. Vi behöver inget formellt bevis på att P inte är lika med NP för att kunna lita på gissningarna, säger Aaronson. Programmerare känner till problemet och skulle vara glada över att se att P inte är lika med NP bevisat, men på en daglig nivå vet de att det är mycket mer meningsfullt att omformulera [ett NP-problem] till något enklare än att försöka lösa det matematiska århundradets problem.
Eftersom problem i NP-klass är så genomgripande (även sudoku-pussel och flygplanssökningar på Bing.com är beräkningsmässigt svåra), upptäcks ständigt innovativa lösningar. Stokastisk optimering, till exempel, härmar slumpmässigheten som finns i fysiska system (som kylande metaller eller muterande DNA) för att producera tillräckligt bra lösningar istället för beräkningshårda.
Försök att klara av antagandet att P inte är lika med NP hjälper oss att utveckla nya mentala teknologier, säger Richard Lipton , en datavetare vid Georgia Tech som studerar P kontra NP-problemet. Även om vi har skrivit algoritmer i decennier förstår vi inte helt vad de kan, fortsätter han. Så även om du bevisade att P inte är lika med NP – något som alla redan tror – så måste det radikalt utöka vår förståelse för dessa förmågor och göra många nya saker möjliga med datorer, förutom alla smarta lösningar vi redan har hittades.
Så om inkrementella framsteg fortfarande kan generera användbar innovation, varför är inte titaner av industriell forskning som Google, Microsoft och HP (som alla avböjde att kommentera för den här artikeln) som ägnar enorma team av forskare åt P inte lika med NP-pussel? Att bevisa ett negativt är bara otroligt svårt, och från [ett stort företags] synvinkel har det förmodligen inte någon större inverkan på nästa finansiella kvartal eller ens de närmaste åren av deras verksamhet, säger Lipton. Det är mer en långsiktig fråga.
Naturligtvis finns det alltid alternativet: att bevisa att P gör faktiskt lika NP. Men håll inte andan, säger Aaronson. Det finns goda skäl till att väldigt få tror att P är lika med NP, säger han. Om det gjorde det, skulle vi leva i ett fundamentalt annorlunda universum, och vi skulle förmodligen ha märkt det nu.