P versus NP

Lisbeth lovede mere om P versus NP.  Her er en forklaring fra mig (jeg er lektor i datalogi)

Beslutningsproblemer er problemer, hvor svaret er ja eller nej. Eksempler er:

“Er tallet x et primtal?”
“Standser algoritme A for input w?”

Siden 1936 har man vidst, at en stor klasse af beslutningsproblemer ikke vil kunne besvares af nogen algoritme. Heldigvis findes der dog også beslutningsproblemer, der kan besvares med en algoritme.

I teoretisk datalogi klassificerer man beslutningsproblemer efter, hvor hurtig den hurtigste løsningsalgoritme er. Hastighed kalder vi tidskompleksitet. Tidskompleksitet måles i antal skridt, som algoritmen bruger som funktion af inputtets længde.

Hvis en løsningsalgoritme har en tidskompleksitetsfunktion, der er opadtil begrænset af et polynomium, siger vi, at algoritmen har polynomiel tidskompleksitet.

Klassen af beslutningsproblemer med løsningsalgoritmer, der har polynomiel tidskompleksitet, kaldes for P.

Hvis man tillader sin løsningsalgoritme at lave tilfældige gæt undervejs, taler man om en nondeterministisk løsningsalgoritme.

Klassen af beslutningsproblemer med nondeterministiske løsningsalgoritmer, der har polynomiel tidskompleksitet, kaldes for NP.

Det er klart at P er en delklasse af NP, men ingen ved, om de to klasser af problemer falder sammen. Dette problem har været åbent siden 1971.

Det er lykkedes at identificere en stor klasse af såkaldt NP-fuldstændige problemer, der har det til fælles, at de er de “sværeste” problemer i NP. Hvis blot ét af disse problemer viser sig også at være i P, ved vi, at P=NP. Hvis omvendt ét af de NP-fuldstændige problemer er uden for P, ved vi, at P og NP er forskellige.

I lighed med andre store åbne problemer i matematisk forskning har P=NP-problemet ført til udviklingen af megen interessant matematisk teori, her specielt hele det område, der hedder kompleksitetsteori.

Personligt ville jeg ikke give mig til at forsøge at løse P=NP-problemet, fordi jeg var deprimeret. Risikoen for, at jeg ikke fandt løsningen og derfor blev endnu mere deprimeret, er nemlig foruroligende høj.

Hans Hüttel www.cs.aau.dk/~hans