kontrol er nemmere end at finde?
at finde en løsning på et problem bør være sværere end at kontrollere, at en løsning er korrekt. Det synes indlysende, hvis du nogensinde har løst en sudoku puslespil, eller løst en Rubiks terning, eller spillet et spil skak. Men denne erklæring, uanset hvor intuitiv udseende, fører os direkte til et af de dybeste matematiske spørgsmål, som vores civilisation stiller.
ikke-deterministisk polynomial tid (eller NP) problemer er dem, hvor du nemt kan kontrollere et svar for at være korrekt., I modsætning hertil polynomial tid (eller P) problemer er dem
Hvor at finde svaret er let. Hvis du kan finde svaret, så har du kontrolleret det for at være korrekt, så ethvert problem I P er også i NP. Vi siger, at P er en underklasse af NP. Vi ved dog ikke, om der er noget særligt problem i NP, der ikke er i P, og det er det, vi kalder p vs NP-problemet.
p vs NP-problemet er et af de mest centrale uløste problemer i matematik og teoretisk datalogi. Der er endda en Clay Millennium-pris, der tilbyder en million dollars til sin løsning., Imidlertid, der er sandsynligvis meget lettere måder at blive millionær end at løse P vs NP!
Der var en brummer for nylig, da nogen hævdede at løse det på ar .iv, selvom der hurtigt blev fundet et hul i beviset. I betragtning af den seneste interesse i problemet og dets centrale plads i matematik, jeg diskutere det i denne uges blog.
Sudoku
Hvis du får et udfyldt Sudoku-puslespil i en avis, kan du smide det i skraldespanden. Men hvis du ville, kunne du scanne gennem rækkerne, kolonnerne og 3 3 3 celler for at fortælle, at det er en gyldig løsning: hver af 1, 2,…, 9 skal forekomme nøjagtigt en gang., Det er analogt med NP, da det er relativt let at kontrollere, om en løsning er korrekt.
men hvis jeg giver dig et delvist fyldt Sudoku-puslespil, kan det være svært at finde løsningen. Det er glæden og udfordringen ved denne slags puslespil. Så at være i NP synes ikke umiddelbart at betyde, at problemet har en let at finde en løsning. Denne intuition er kernen i P vs NP-problemet.
Præcis formulering
for At forstå, P og NP mere præcist, er vi nødt til bedre at forstå algoritmer og måle deres hastighed. Problemer er forbundet med nogle faste input og output enten ja eller nej. Indgangen er en given længde, siger n, hvor n er et positivt heltal. Dette repræsenterer antallet af bits, det tager at udtrykke input. En algoritme er en metode eller procedure til løsning af et problem. Algoritmer giver instruktioner på hvert trin i en beregning og skal opsige., Trinene kan være sekunder, millisekunder eller et andet fast tidsinterval, der afhænger af dit problem.
kompleksiteten af et problem er den mindste worstorst-case køretid over alle mulige algoritmer løse problemet som en funktion af længden af input. Med andre ord måler det, hvor lang tid det tager at løse problemet med den hurtigste algoritme, men med det værste tilfælde input.
et problem kan løses i polynomisk tid hvis der gives et input af længde n, er dets kompleksitet afgrænset ovenfor af polynomfunktionen nm for nogle ikke-negative heltal m., Sættet af alle problemer, der kan løses i polynomisk tid, betegnes af P.
at være i P betyder ikke nødvendigvis, at problemet er muligt. For eksempel, hvis det tager n1000 trin for at køre algoritmen, så vil det være håbløst langsom, selv for små n. Ikke-deterministisk polynomium (eller NP) problemer er dem, hvor du kan tjekke, hvis JA svaret er korrekt i polynomiel tid.
NP-hårdhed
et problem er NP–hard, hvis en polynomial-tid algoritme for det ville indebære en polynomial-tid algoritme for hvert problem i NP. Derfor, hvis et NP-hårdt problem var i P, så P = NP., NP-hard-problemerne er mindst lige så hårde som ethvert problem i NP. Et NP-komplet problem er et, der er NP-hard og i NP.
et klassisk NP-komplet problem er at finde en Hamilton-cyklus. Antag, at vi har et netværk af byer forbundet med veje. Problemet er at besøge hver by ved hjælp af veje (ingen fly tilladt!) og kom tilbage til starten. Dette synes let for et lille antal byer, men hvis du fik hundredvis af dem så bliver det svært., Tusindvis af andre sådanne NP-komplette problemer er kendt opstår i grafteori, talteori, geometri, og andre områder af matematik og datalogi.
hvad er svaret, virkelig?
Hvis jeg skulle satse, ville jeg antage, at P ikke svarer til NP, og jeg tror, at de fleste eksperter ville være enige. Vi skulle være forfærdeligt dumme for ikke at se, hvordan alle de tusindvis af NP-komplette problemer ikke har en polynomial tidsalgoritme. Men som en art er dum vores standardposition, så ingen kan sige, hvad svaret er med 100% sikkerhed.,
det, der er interessant ved P vs NP-problemet, er, at det peger på, hvor begrænset vores forståelse er i at bevise, at visse problemer ikke har hurtige løsninger. Dette er en del af et større tema inden for beregningskompleksitetsteori, der studerer snesevis af andre kompleksitetsklasser. Tjek kompleksiteten zoo for en liste over disse klasser. For det meste er det åbent for at vise forskellige (ofte eksotiske klingende) kompleksitetsklasser er korrekte underklasser af hinanden. For eksempel er det ukendt, om NL er en ordentlig underklasse af P, og vi ved ikke, om FPT er en ordentlig underklasse af W..,
uanset dets ægthed vil p vs NP-problemet sandsynligvis forblive åbent i nogen tid. Medmindre det er bevist, at P = NP, forbliver Sudoku sikkert.
Anthony Bonato