Hvad er årtusindeproblemet?
Q: Hvad er årtusindeproblemet?
A: Millennium-problemet er et af de vigtigste og mest udfordrende matematiske problemer i dette århundrede, der handler om, hvorvidt alle problemer, der er lette for computere at verificere, også er lette at løse.
Q: Hvordan kan vi klassificere matematiske problemer?
A: Matematiske problemer kan klassificeres som P- eller NP-problemer baseret på, om de kan løses i endelig polynomiel tid.
Q: Hvad er forskellen mellem P- og NP-problemer?
Svar: P-problemer er relativt hurtige og "nemme" for computere at løse, mens NP-problemer er hurtige og "nemme" for computere at kontrollere, men ikke nødvendigvis nemme at løse.
Q: Hvem introducerede P versus NP-problemet?
A: Stephen Cook introducerede P versus NP-problemet i 1971 i sin artikel "The complexity of theorem proving procedures."
Spørgsmål: Hvorfor er P versus NP-problemet vigtigt?
A: P versus NP-problemet betragtes som det vigtigste åbne problem inden for datalogi og er et af de syv Millennium Prize Problems med en præmie på 1.000.000 dollars for en løsning, der inviterer til en offentliggjort anerkendelse af Clay Institute og formodentlig en eller flere, der ændrer hele matematikken.
Q: Er det muligt at løse et NP-komplet problem på kvadratisk eller lineær tid?
A: I 1956 skrev Kurt Gödel et brev til John von Neumann, hvor han spurgte, om et bestemt NP-komplet problem kunne løses på kvadratisk eller lineær tid.
Q: Hvorfor håber mange matematikere, at årtusindeproblemerne hænger sammen?
A: Mange af årtusindeproblemerne berører relaterede emner, og det er mange matematikeres drøm at opfinde forenende teorier.
