kontroll är lättare än att hitta?
att hitta en lösning på ett problem bör vara svårare än att kontrollera att en lösning är korrekt. Det verkar uppenbart om du någonsin har löst ett sudoku pussel, eller löst en Rubiks kub, eller spelat ett schackspel. Men det uttalandet, men intuitivt utseende, leder oss direkt till en av de djupaste matematiska frågorna som vår civilisation ställer.
icke-deterministiska polynomialtid (eller NP) problem är de där du enkelt kan verifiera ett svar för att vara korrekt., Däremot är polynom tid (eller P) problem de
där det är lätt att hitta svaret. Om du kan hitta svaret har du kontrollerat att det är korrekt, så varje problem i P finns också i NP. Vi säger att P är en underklass av NP. Vi vet dock inte om det finns något särskilt problem i NP som inte finns i P, och det är vad vi kallar p vs NP-problemet.
p vs NP-problemet är ett av de mest centrala olösta problemen i matematik och teoretisk datavetenskap. Det finns även en lera Millennium pris som erbjuder en miljon dollar för sin lösning., Det finns dock sannolikt mycket enklare sätt att bli miljonär än att lösa P vs NP!
det var en buzz nyligen när någon påstod sig lösa det på arXiv, även om ett gap i beviset snabbt hittades. Med tanke på det senaste intresset för problemet och dess centrala plats i matematik diskuterar jag det i veckans blogg.
Sudoku
om du får ett fyllt Sudoku-pussel i en tidning kan du kasta det i papperskorgen. Men om du vill kan du skanna igenom raderna, kolumnerna och 3 x 3-cellerna för att berätta att det är en giltig lösning: var och en av 1, 2, … , 9 måste ske exakt en gång., Det är analogt med NP, eftersom det är relativt lätt att kontrollera om en lösning är korrekt.
men om jag ger dig en delvis fylld Sudoku pussel, kan det vara svårt att hitta lösningen. Det är glädjen och utmaningen av denna typ av pussel. Så att vara i NP verkar inte omedelbart innebära att problemet har en lätt att hitta en lösning. Den intuitionen ligger i hjärtat av p vs NP-problemet.
exakt formulering
för att förstå P och NP mer exakt måste vi bättre förstå algoritmer och mäta deras hastighet. Problem uppstår med viss fast ingång och utgång antingen ja eller nej. Ingången är en given längd, säg n, där n är ett positivt heltal. Detta representerar antalet bitar som krävs för att uttrycka ingången. En algoritm är en metod eller ett förfarande för att lösa ett problem. Algoritmer ger instruktioner vid varje steg i en beräkning och måste avsluta., Stegen kan vara sekunder, millisekunder eller något annat fast tidsintervall som beror på ditt problem.
komplexiteten i ett problem är minsta värsta fall körtid över alla möjliga algoritmer lösa problemet som en funktion av längden på ingången. Med andra ord mäter det hur lång tid det tar att lösa problemet med den snabbaste algoritmen men med värsta fall inmatning.
ett problem är lösbart i polynomtid om det ges en inmatning av längd n, begränsas dess komplexitet ovan av polynomfunktionen nm för vissa icke-negativa heltal m., Uppsättningen av alla problem lösbara i polynom tid betecknas med P.
att vara i P betyder inte nödvändigtvis att problemet är möjligt. Till exempel, om det tar N1000 steg för att köra algoritmen, så blir det hopplöst långsamt även för små n. icke-deterministiska polynom (eller NP) problem är de där du kan kontrollera om ja svaret är korrekt i polynom tid.
NP–hårdhet
ett problem är NP-hard om en polynomialtidsalgoritm för det skulle innebära en polynomialtidsalgoritm för varje problem i NP. Därför, om ett NP-hårt problem var i P, då P = NP., De NP-hårda problemen är minst lika svåra som alla problem i NP. Ett NP-komplett problem är en som är NP-hård och i NP.
ett klassiskt NP-komplett problem är att hitta en Hamilton-cykel. För detta, anta att vi har ett nätverk av städer anslutna med vägar. Problemet är att besöka varje stad med hjälp av vägar(inga plan tillåtna!) och kom tillbaka till början. Detta verkar lätt för ett litet antal städer, men om du fick hundratals av dem blir det svårt., Tusentals andra sådana NP-kompletta problem är kända som uppstår i grafteori, nummerteori, geometri och andra områden inom matematik och datavetenskap.
vad är svaret egentligen?
om jag skulle satsa, skulle jag anta att P inte motsvarar NP, och jag tror att de flesta experter skulle hålla med. Vi måste vara väldigt dumma för att inte se hur alla tusentals NP-kompletta problem inte har en polynomialtidsalgoritm. Men som art är dum vår standardposition så ingen kan säga vad svaret är med 100% säkerhet.,
det som är intressant med p vs NP-problemet är att det pekar på hur begränsad vår förståelse är för att bevisa att vissa problem inte har snabba lösningar. Detta är en del av ett större tema inom området beräkningskomplexitet teori, som studerar dussintals andra komplexa klasser. Kolla in komplexiteten zoo för en lista över dessa klasser. För det mesta är det öppet att visa olika (ofta exotiska ljud) komplexitetsklasser är korrekta underklasser av varandra. Det är till exempel okänt om NL är en riktig underklass av P, och vi vet inte om FPT är en riktig underklass av W.,
oavsett dess sanningsenlighet kommer P vs NP-problemet sannolikt att förbli öppet under en tid. Om det inte är bevisat att P = NP, Sudoku förblir säker.
Anthony Bonato