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.