Mikä on vuosituhannen vaihteen ongelma?
K: Mikä on vuosituhannen vaihteen ongelma?
V: Millennium-ongelma on yksi tämän vuosisadan tärkeimmistä ja haastavimmista matemaattisista ongelmista, joka käsittelee kysymystä siitä, onko jokainen ongelma, joka on tietokoneiden helppo todentaa, myös helppo ratkaista.
K: Miten voimme luokitella matemaattisia ongelmia?
V: Matemaattiset ongelmat voidaan luokitella P- tai NP-ongelmiksi sen perusteella, ovatko ne ratkaistavissa äärellisessä polynomiajassa.
K: Mitä eroa on P- ja NP-ongelmien välillä?
V: P-ongelmat ovat suhteellisen nopeita ja "helppoja" tietokoneiden ratkaistavaksi, kun taas NP-ongelmat ovat nopeita ja "helppoja" tietokoneiden tarkistettavaksi, mutta eivät välttämättä helppoja ratkaista.
K: Kuka esitteli P versus NP-ongelman?
V: Stephen Cook esitteli P versus NP-ongelman vuonna 1971 artikkelissaan "The complexity of theorem proving procedures".
K: Miksi P vs. NP-ongelma on tärkeä?
V: P vs. NP -ongelmaa pidetään tietojenkäsittelytieteen tärkeimpänä avoimena ongelmana, ja se on yksi seitsemästä Millennium Prize Problems -ongelmasta, jonka ratkaisusta, joka kutsuu Clay-instituutin julkaistun tunnustuksen ja oletettavasti koko matematiikkaa muuttavan ratkaisun (ratkaisut), jaetaan 1 000 000 dollarin palkinto.
Kysymys: Onko mahdollista ratkaista NP-täydellinen ongelma kvadraattisessa tai lineaarisessa ajassa?
V: Vuonna 1956 Kurt Gödel kirjoitti John von Neumannille kirjeen, jossa hän kysyi, voidaanko tietty NP-täydellinen ongelma ratkaista kvadraattisessa tai lineaarisessa ajassa.
K: Miksi monet matemaatikot toivovat, että vuosituhannen vaihteen ongelmat liittyvät toisiinsa?
V: Monet vuosituhannen vaihteen ongelmista koskevat toisiinsa liittyviä kysymyksiä, ja monien matemaatikkojen unelma on keksiä yhdistäviä teorioita.
