P=NP, siger Knuth

hex

Da jeg studerede, var der et spil, vi ofte spillede, nemlig Hex. Spillet blev opfundet af Piet Hein tilbage i 1942 og spilles af to mennesker (vi kan jo kalde dem rød og blå) med blyant og ovenstående spillebræt på et stykke papir. Hver spiller har to modstående sider af rhomben.

De to spillere skiftes til at afkrydse et felt. Målet er at blive den første, der kan lave en ubrudt følge af krydser der forbinder de to modstående sider.

I 1949 viste John Nash (ham fra A Beautiful Mind) at der er vindende strategi i Hex men han viste ikke hvordan sådan en strategi ser ud! Man ved hvordan vindende strategier ser ud op til 9 gange 9 felter, derefter ved man ikke noget endnu. Hvis man skal se positivt på det, betyder det at det stadig bør være sjovt at spille Hex.

Men den slags ikke-konstruktive argumenter bør få én til at tænke. Det er underligt at vide at der findes et bestemt objekt (som her er en strategi) men ikke at vide hvordan det ser ud.

Der er et interessant interview med den legendariske datalog og matematiker Donald Knuth hvor han bruger Hex som del af en begrundelse for at tro at \mathrm{P=NP}-formodningen har et positivt svar, dvs. at \mathrm{P=NP}. Det er der ellers ikke så mange, der mener. Knuth er til gengæld tilbøjelig til at mene at der er et ikke-konstruktivt bevis for sætningen.

As you say, I’ve come to believe that \mathrm{P=NP}, namely that there does exist an integer M and an algorithm \mathcal{A} that will solve every n-bit problem belonging to the class \mathrm{NP} in n^M elementary steps.

Some of my reasoning is admittedly naïve: It’s hard to believe that \mathrm{P \neq NP} and that so many brilliant people have failed to discover why. On the other hand if you imagine a number M that’s finite but incredibly large—like say the number 10 3 discussed in my paper on “coping with finiteness”—then there’s a humongous number of possible algorithms that do n^M bitwise or addition or shift operations on n given bits, and it’s really hard to believe that all of those algorithms fail.

My main point, however, is that I don’t believe that the equality \mathrm{P=NP} will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive. Although I think M probably exists, I also think human beings will never know such a value. I even suspect that nobody will even know an upper bound on M.

Er det så et godt argument at sige at “Jeg kan ikke forestille mig at det ikke er tilfældet”? Jeg ved det ikke rigtig, men det er interessant og (synes jeg) også lidt skræmmende hvis \mathrm{P=NP} og vi ikke kan få glæde af den viden.

(Visited 70 times, 1 visits today)
Loading Facebook Comments ...

Én kommentar til “P=NP, siger Knuth”

Skriv et svar