Izvor: Politika, 21.Avg.2010, 01:14 (ažurirano 02.Apr.2020.)
Glavolomka od milion dolara
Indijac Vinađ Kumar Deolalikar, zaposlen u „Hjulit-Pakardu”, upravo je obelodanio da je odgonetnuo jednu od šest najtežih matematički zagonetki. Ukoliko niste pohlepni, poslušajte, svakako, savet Tomasa Mana
Znate li kako da zaradite svoj prvi milion dolara? A posle sve ide kao po loju, to ste više puta čuli od mnogih svetskih bogataša. Ali ni od jednog našeg, pa se nameće zaključak da su ga mukotrpno sticali!
Odgovor je jednostavan: odgonetnite jednu >> Pročitaj celu vest na sajtu Politika << od šest preostalih zagonetki koje godinama zadaju veliku glavobolju svim matematičarima sveta. Možda samo pet, ukoliko se pokaže da je Vinađ Kumar Deolalikar, matematičar iz „Hjulit-Pakardove” laboratorije, ovih dana rešio prvu sa liste Klejovog matematičkog instituta (SAD). Upravo je obelodanio svoj dokaz: „P” nije jednako „NP” (P versus NP ili P ≠ NP). Glavolomku su 1971. godine smislila dvojica matematičara, Stiven Kuk i Leonid Levin, kada se on rodio u Nju Delhiju (Indija).
Mladi indijski naučnik je u svojem članku, koji je volšebno dospeo na Internet, obrazložio da „P” nije jednako „NP”. U međuvremenu je nalaz poslao vodećim znalcima u svetu, čije opaske iščekuje. Sudeći na osnovu prethodnih radova, u kojima je dokazao da je „P” manje od „NP” za beskonačne Tjuringove mašine, može se nadati povoljnom odzivu. Većina računarskih naučnika, inače, već dugo veruje da su „P” i „NP” različite klase problema.
400 studenata u 100 soba
Britanski matematičar Alan Tjuring uveo je 1936. formalnu izračunljivost pre pojave samog računara. Postojanje univerzalne Tjuringove mašine najavilo je da moguće napraviti univerzalni računar, spravu koja izvršava proizvoljan algoritamski zadatak.
„P prema NP” postavlja pitanje postoje li problemi čiju je istinitost rešenja lako proveriti, iako sam nije lako rešiv. Danas je to jedan od najkrupnijih i najpoznatijih izazova u računarskim naukama. Matematička izračunavanja, naime, podrazumevaju proveru neobično velikog broja mogućih ishoda, što uveliko premašuje moć sadašnjih kompjutera.
Matematičke probleme iz klase „P” smatraju laganim, zato što se može napisati brzi program koji će to rešavati. Na raspolaganju su, dakle, algoritmi (konačan niz koraka za rešavanje) s polinomijskom složenošću. Jedan od primera jeste provera da li je neki broj prost. Ali ima teško rešivih problema, svrstanih u klasu „NP”, za koje se nije znalo da li su izvodljivi algoritmi za brzo rešavanje.
Vinađ Kumar Deolalikar smatra da je dokazao da „P”, koji se tiče problema čija se rešenja lako nalaze i potkrepljuju, nije isto što i „NP”, koji se odnosi na probleme čije je rešenje gotovo nemoguće naći, ali su lagani za potvrđivanje.
Glavolomna zagonetka nastala je, kao što smo rekli, 1971. godine. Da bi se shvatilo koliko je nerazmrsiva, potkrepićemo to uzorkom za rešavanje koji je Klejov matematički institut predložio. Izračunajte kako da razmestite 400 studenata u 100 univerzitetskih soba, uz uslov da zajedno ne stavite „nespojive parove”. Za utehu: ukupan iznos mogućih izbora nadmašuje broj atoma u poznatom kosmosu!
Hoće li ijedna buduća civilizacija ikada načiniti superkompjuter koji je u stanju da to izračuna, zato što mora da ima na raspolaganju neverovatno dugo vreme?
Hilbert, Man i novobogataši
Klejov matematički institut iz Kembridža (SAD), privatna neprofitna zadužbina, osnovao je 1998. imućni poslovni čovek Lendon Klej s namerom da uveća i raširi matematičko znanje i da ovenča visoka dostignuća. Prvo odličje dodelio je sledeće godine Endruu Vajlsu, jednom od najslavnijih matematičara današnjice, koji je otkrio dokaz za čuvenu „Fermaovu poslednju teoremu” (Francuski pravnik Pjer Ferma), tri i po stoleća nerešenu!
Idući u susret novom hiljadugodištu, ustanovio je „Milenijumsku nagradu” u iznosu od po milion dolara za odgonetanje svakog od sedam najtežih matematičkih izazova 21. veka: „P prema NP”, „Hodžova hipoteza”, „Poenkareova hipoteza” (dokaz je na Internetu objavio ćudljivi ruski genije Igor Pereljman koji je odbio i kolajnu i novac), „Rimanova hipoteza”, „Jang–Milsova teorija”, „Navijer–Stouksova jednačina” i „Birčova i Svinerton-Dijerova hipoteza”.
Uzor mu je, po svemu sudeći, bio čuveni spisak 23 važna problema koji je nenadmašni nemački matematičar David Hilbert (1862–1943) 1900. predstavio Svetskom kongresu matematičara u Parizu. Ostala je upamćena njegova blistava opaska: Da sam se sada probudio, posle sna od hiljadu godina, moje prvo pitanje bilo bi: da li je Rimanova hipoteza dokazana? Pojedini ni do dan-danas nisu razmršeni, pa ni „Rimanova hipoteza”.
Ukoliko ste se popišmanili, utešite se rečima Tomasa Mana: „Kažem im da će uvideti da je najbolji lek protiv pohlepe i pohote ako se zaokupe učenjem matematike.” Da li je to savet i za naše novobogataše?
Stanko Stojiljković
objavljeno: 21/08/2010
