P=NP og Hilberts basissætning

pudlak

Et af de emner, som mange inden for datalogi og matematik ynder at tale om er \mathrm{P=NP}-problemet. Problemet er underligt fristende og frustrerende; vi kender problemet godt nok til at kunne formulere det præcist, men løsningen kender vi ikke. Det er lidt som det pæretræ, der står et sted i min svigerfars have; fem meter oppe sidder der hvert år en masse flotte pærer. Men stammen er helt lige og med få grene.

Jeg kan ikke lade være med at tænke på hvordan andre åbne problemer i matematik først er blevet løst efter at der er kommet ny og overraskende indsigt. Bagefter kom standardpensum og lærebøgerne. Et af de helt store problemer i 1800-tallets matematik var det, vi nu kender som Hilberts basissætning i algebra. Er det tilfældet at hvis R er en Noethersk ring, da er ethvert ideal i polynomiumsringen R[x_1,\ldots,x_n] endeligt frembragt? Hermed menes der at der skal findes der en endelig mængde \{k_1,\ldots,k_m\} af elementer i idealet M, således at ethvert element i det kan skrives som en linearkombination af dem.

En Noethersk ring R er en ring, hvor enhver ikke-tom familie af idealer fra R har et maksimalt element. Legemer (men såmænd også bare den sædvanlige ring over  \mathbb{Z}) er eksempler på Noetherske ringe.

Vi har med andre ord at gøre med begreber, som man i dag lærer i algebrakurset på første del af en matematikuddannelse. Så dette problem er inden for rækkevidde på samme måde som \mathrm{P=NP}-problemet er det for datalogistuderende.

Hilberts bevis var et snedigt induktionsbevis – og ikke-konstruktivt. Det er bestemt ikke en overdrivelse at sige, at ikke alle var glade for at dét var tilfældet. Også beviset er i dag inden for rækkevidde af en studerende på første del af en matematikuddannelse. (Senere er der kommet konstruktive beviser for udgaver af basissætningen.)

Klaus Frovin Jørgensen har en gennemgang af hvad Hilberts basissætning førte med sig. På nogle måder er konstruktiv matematik og alt det, den har ført med sig, en reaktion mod Hilberts ikke-konstruktive tilgang. Jeg tror selv at et bevis for \mathrm{P=NP}-problemet vil føre til et lignende jordskred og at beviset for at \mathrm{P=NP} (eller for at \mathrm{P \neq NP}) en dag bliver del af pensum på datalogiuddannelsen. Om jeg så selv når at komme til at undervise i det, er en helt anden snak.

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

Skriv et svar