Hva er tusenårsproblemet?
Q: Hva er tusenårsproblemet?
A: Tusenårsproblemet er et av de viktigste og mest utfordrende matematiske problemene i dette århundret, og det dreier seg om hvorvidt alle problemer som er enkle å verifisere for datamaskiner, også er enkle å løse.
Q: Hvordan kan vi klassifisere matematiske problemer?
Svar: Matematiske problemer kan klassifiseres som P- eller NP-problemer basert på om de kan løses på endelig polynomisk tid.
Q: Hva er forskjellen mellom P- og NP-problemer?
Svar: P-problemer er relativt raske og "enkle" for datamaskiner å løse, mens NP-problemer er raske og "enkle" for datamaskiner å sjekke, men ikke nødvendigvis enkle å løse.
Spørsmål: Hvem introduserte P versus NP-problemet?
Svar: Stephen Cook introduserte P versus NP-problemet i 1971 i artikkelen "The complexity of theorem proving procedures".
Spørsmål: Hvorfor er P versus NP-problemet viktig?
Svar: P versus NP-problemet regnes som det viktigste åpne problemet innen datavitenskapen og er et av de syv Millennium Prize Problems, med en pris på 1 000 000 dollar for en løsning som innbyr til en publisert anerkjennelse fra Clay Institute og antagelig en løsning som endrer hele matematikken.
Q: Er det mulig å løse et NP-komplett problem på kvadratisk eller lineær tid?
Svar: I 1956 skrev Kurt Gödel et brev til John von Neumann der han spurte om et bestemt NP-komplett problem kunne løses på kvadratisk eller lineær tid.
Q: Hvorfor håper mange matematikere at tusenårsproblemene henger sammen?
A: Mange av tusenårsproblemene berører beslektede problemstillinger, og det er mange matematikeres drøm å finne opp teorier som forener dem.
