Mis on aastatuhande probleem?
K: Mis on aastatuhande probleem?
V: Millenniumiprobleem on üks selle sajandi tähtsamaid ja keerulisemaid matemaatilisi probleeme, mis käsitlevad küsimust, kas iga probleem, mida on arvutite jaoks lihtne kontrollida, on ka lihtne lahendada.
K: Kuidas saab matemaatilisi probleeme liigitada?
V: Matemaatikaprobleeme saab liigitada P- või NP-probleemideks selle põhjal, kas need on lahendatavad piiratud polünoomiaja jooksul.
K: Mis vahe on P- ja NP-probleemidel?
V: P-probleemid on arvutite jaoks suhteliselt kiiresti ja "lihtsalt" lahendatavad, samas kui NP-probleemid on arvutite jaoks kiiresti ja "lihtsalt" kontrollitavad, kuid mitte tingimata kergesti lahendatavad.
K: Kes võttis kasutusele P versus NP probleemi?
V: Stephen Cook tutvustas P versus NP probleemi 1971. aastal oma artiklis "The complexity of theorem proving procedures".
K: Miks on P versus NP probleem oluline?
V: P versus NP probleemi peetakse arvutiteaduse tähtsaimaks avatud probleemiks ja see on üks seitsmest aastatuhande auhinna probleemist, mille lahenduse eest, mis kutsub üles Clay instituudi poolt avaldatud tunnustuse ja eeldatavasti kogu matemaatikat muutva(te) lahenduse(te) eest, on välja pandud 1 000 000 dollari suurune auhind.
Küsimus: Kas on võimalik lahendada NP-täielik probleem kvadraatilise või lineaarse ajaga?
V: 1956. aastal kirjutas Kurt Gödel John von Neumannile kirja, milles küsis, kas teatud NP-komplektset probleemi saab lahendada kvadraatilise või lineaarse ajaga.
K: Miks loodavad paljud matemaatikud, et aastatuhande probleemid on omavahel seotud?
V: Paljud aastatuhande probleemid puudutavad omavahel seotud küsimusi ja paljude matemaatikute unistuseks on leiutada ühendavad teooriad.
