Sedam problema tisućljeća. Od problema kuhara do problema putnika! Što znači financijski poticaj?

Möbiusova traka se ponekad pogrešno naziva trakom. To je netočno jer traka treba biti ograničena na dvije krivulje, odnosno rubove. Kao što možete lako vidjeti, Möbiusova traka nema samo jednu stranu, ona također ima samo jedan rub. Uz ovaj rub može se zalijepiti u kuglu ako se u njoj izreže rupa. Dobivena ploha naziva se projektivna ravnina. Ona nije samo dvodimenzionalna, poput površine sfere ili torusa, već i jednostrana, poput površine Möbiusove trake. Osim toga, ne može se ugraditi u obični trodimenzionalni prostor, pa se stoga ne može zamisliti izvan ljudske moći. Fotografija (Creative Commons licenca): Dave Gough

Koliko je već rečeno o tome da ruski znanstvenici, unatoč svim svojim kvalifikacijama, primaju mizerne plaće. Ipak, upravo su znanstvenici, za razliku od raznih vrhunskih menadžera, pop zvijezda i supersportaša, u stanju doslovno preko noći zaraditi milijun dolara. Da biste to učinili, trebate samo sjesti, razmisliti i riješiti jedan od matematičkih “problema tisućljeća”.

Zašto je problem

U odnosu na prošlo stoljeće, broj takvih problema smanjio se gotovo četiri puta. Kada je na samom početku 20. stoljeća slavni njemački matematičar David Hilbert (1862.-1943.) govorio na međunarodnom matematičkom kongresu u Parizu, popis matematičkih i logičkih problema koje je iznio, a koje je trebalo riješiti u sljedećih stotinu godina, uključivao je 23. stavke. Plus još tri problema s kojima je započeo svoj govor, a koji, već spomenuti, nisu uvršteni u glavni popis. Hilbertu su se činile tako očigledne. A jedan od najljepših - problem ekvivalencije poliedara istog volumena - riješen je nekoliko godina prije nego što ga je Hilbert postavio.

Prvi problem koji je spomenuo i posljednji problem koji je riješio (ukupno ih je dvadesetak potpuno riješeno do kraja stoljeća) bio je dokaz slavnog Fermatovog posljednjeg teorema. Dva su preostala problema djelomično riješena, dva su još otvorena, jedan, o matematičkom opisu fizikalnih aksioma, prepoznat je kao nematematički, a jedan, o ravnoj liniji kao najkraćoj vezi dviju točaka, proglašen je nedorečenim. , što je onemogućilo razumijevanje, riješila ona ili ne.

Novi popis problema, sastavljen početkom ovog stoljeća, sadrži samo sedam zadataka. Temeljna razlika između sadašnjeg popisa, nazvanog “Problemi milenijske nagrade”, jest u tome što je za rješavanje svakog od njih privatna neprofitna zaklada koju je 1998. godine u Cambridgeu u SAD-u osnovao bostonski biznismen Landon T. Clay, imenovala Nagrada od milijun kuna, naprotiv: odabrano je točno sedam problema prema broju milijuna dodijeljenih za njihovo rješavanje. Rješavanje Hilbertovih problema nije podrazumijevalo nikakvu nagradu osim vječne znanstvene slave i dubokog znanstvenog zadovoljstva.

Što znači financijski poticaj?

Clayev prvi milijun dodijeljen je 18. ožujka 43-godišnjem ruskom matematičaru i bivšem suradniku Grigoriju Yakovlevichu Perelmanu, koji je dokazao valjanost takozvane Poincaréove pretpostavke.

Ako preko lopte nategnete elastičnu traku, pa ju postupnim zatezanjem, a da je nigdje ne pokidate ili otkinete s površine, skupite u jednu točku. Zatim kažu o tome da je "homotopno nuli". Ako povučete takvu vrpcu na krafnu, isti trik možda više neće funkcionirati: neće svaka krivulja na krafni biti homotopna nuli.

Sudbina preostalih milijuna

Birchova i Swinerton-Dyerova pretpostavka

Jednadžbe oblika x n + y n + z n + … = t n na skupu cijelih brojeva privlačile su pozornost matematičara od davnina. Rješenje najjednostavnijeg od njih x 2 + y 2 = z 2 (na primjer, poznati “egipatski trokut” - 3 2 + 4 2 = 5 2) bilo je poznato još u Babilonu, a potpuno je istraženo još u 3. stoljeća naše ere. e. Aleksandrijski matematičar Diofant (Διόφαντος ὁ Ἀλεξανδρεύς, Diofant, 3. st. n. e.). Pierre Fermat je na marginama svoje “Aritmetike” napisao formulaciju svog poznatog teorema (Pierre de Fermat, 1601. ili 1607/8-1665). A jedno od najvećih rješenja (u eri prije računala) predložio je 1769. Leonhard Euler (1707.-1783.). Uspio je konstruirati sljedeću jednakost: 2 682 440 4 + 15 365 639 4 + 18 796 760 4 = 20 615 673 4.

Ne postoji univerzalna metoda izračuna za takve jednadžbe. Međutim, čak i tijekom dugih neuspješnih pokušaja da se dokaže Fermatov teorem, saznalo se za njihovu povezanost s prostim brojevima, a potom i s nekim klasama ravninskih krivulja. Korijeni Diofantovih jednadžbi, prosti brojevi i sjecišta ravninskih krivulja opisuju se pomoću nekih posebnih funkcija - npr. Riemannove zeta funkcije ili njezinih generalizacija, L-Gasse-Weilove funkcije. Matematičari Bryan John Birch i Sir Henry Peter Francis Swinnerton-Dyer 1960. godine, eksperimentirajući na računalu s nekim dobro poznatim krivuljama, otkrili su prilično jednostavno ponašanje za njih L-funkcije blizu nula. Zatim su pretpostavili da će to svojstvo vrijediti za sve krivulje. Do sada nitko nije uspio niti dokazati niti opovrgnuti ovu pretpostavku. Ako mislite da to ne možete dokazati, pronađite primjer u kojem imovina ne funkcionira, a možete pretpostaviti da imate milijun u džepu. Uostalom, da bi se to dobilo, dovoljno je opovrgnuti hipotezu čak i jednostavnim posebnim slučajem.

Hodgeova pretpostavka

Teže je proučavati složeni objekt što je njegova struktura složenija. Stoga ga matematičari obično prvo pokušavaju rastaviti na jednostavnije objekte s kojima je, kao što je jasno, lakše raditi. Problem je u tome što nije uvijek moguće jednostavno rastaviti objekt na njegove komponente. Ponekad se u ovom slučaju pojavljuju novi dijelovi, nepoznato je odakle su došli i nije jasno što predstavljaju. Ili, naprotiv, detaljnije istraživanje otkriva da neki detalji očito nedostaju. Jednostavno, promatrajući same cigle, ne možemo zamisliti kakva je kuća napravljena od njih, kako izgleda i po kojim se pravilima gradi. Da biste to učinili, morate barem proučiti prazan prostor prostorija između njih. Profesor s Cambridgea William Hodge (William Vallance Douglas Hodge, 1903.-1975.) u svojim je spisima 1941. godine opisao uvjete pod kojima, kako se njemu čini, ne mogu nastati takvi neshvatljivi “suvišni” dijelovi i u kojima se bilo koje geometrijsko tijelo može proučavati kao algebarska jednadžba, stvarajući njezin matematički model. Njegovu pretpostavku znanstvenici ne mogu dokazati niti opovrgnuti gotovo 70 godina.

Navier-Stokesove jednadžbe

Kad brodom plovite po jezeru, iz njega se šire valovi. Prateći avion koji leti ili jureći automobil nastaju turbulentna strujanja - valoviti zračni vrtlozi. Svi ovi fenomeni opisani su Navier-Stokesovim jednadžbama stvorenim davne 1822. godine. Unatoč činjenici da su jednadžbe nastajale dosta dugo, nitko ih još uvijek ne zna riješiti. Štoviše, još nitko ne zna ni postoji li način da ih se uopće riješi. Istodobno, vrlo ih aktivno koriste ne samo matematičari, već i dizajneri zrakoplova, automobila i brodova. Istina, zasad se mogu koristiti samo NT metodom (“znanstvenim bockanjem”): zamjenjujući već poznate vrijednosti brzine, vremena, tlaka, gustoće itd. i provjeravajući odgovaraju li jedna drugoj. Ako netko pronađe metodu rješenja, moći će se koristiti jednadžbe u suprotnom smjeru, računajući sve potrebne parametre iz jednakosti. Ovo će učiniti aerodinamička ispitivanja nepotrebnima. Međutim, matematičar će dobiti nagradu čak i ako dokaže da ne postoji metoda rješenja.

Problem provjere odluke (problem Cook-Lewin)

Ako čovjek dobije zadatak da pronađe blago zakopano tamo u prošlom stoljeću u šumi, na potragu može potrošiti godinu, dvije, desetljeće, pa čak i cijeli život. Sve se odvija mnogo brže kada mu kažu: “Blago je zakopano ispod jedine jasike u šumi. Idi i provjeri." Otprilike isto se događa prilikom rješavanja bilo kojeg problema. Svi dobro razumijemo da provjera rješenja obično traje kraće nego samo rješenje. Razumijemo, ali kako se pokazalo, ne možemo dokazati ovu jednostavnu i naizgled logičnu činjenicu. Stoga, ako uspijete pronaći takav problem, čija će vam provjera ispravnosti rješenja, bez obzira na način provjere, oduzeti više vremena nego samo rješavanje, hitno se obratite Institutu Clay i za dvije godine postat ćete vlasnik od milijun dolara. Rješenje “Cookovog problema” formuliranog 1971. godine, prema znanstvenicima, dovest će do prave revolucije u području kriptografije i do pojave sustava šifriranja koji se jednostavno ne mogu probiti. Vrlo grubo: pojavit će se šifre, čija će provjera ispravnosti razbijanja trajati beskrajno dugo.

Riemannova hipoteza

Među cijelom masom brojeva posebno mjesto zauzimaju brojevi koji se ne mogu podijeliti ni na što manje od sebe: 1, 2, 3, 5, 7, 11, 13, 17 i tako dalje. Takvi brojevi se nazivaju "prim" brojevi i izuzetno su važni matematičarima. Kako su raspoređeni duž numeričkog niza, to zna samo Bog. Riemann 1859. nije čak ni predložio način kako ih pronaći ili testirati. Jedini način da provjerite je li broj prost ili ne jest da ga pokušate podijeliti na sve njegove manje proste brojeve (najveći do sada poznati prosti broj pronađen je u kolovozu 2008. i sastoji se od 12.978.189 znamenki). Jednostavno je pronašao metodu kojom se može odrediti najveći broj prostih brojeva koji ne prelaze određeni zadani broj. Do danas su matematičari testirali ovu metodu s trilijun i pol "jednostavnih". Do sada nisu pronađeni kvarovi. Međutim, to uopće ne znači da se metoda neće spotaknuti na prvih jedan i pol bilijun čeka. A budući da se Riemannova hipoteza, koja je na novi popis prenesena s Hilbertove liste, aktivno koristi za izračun sigurnosnih sustava prijenosa podataka u mobilnim mrežama, na Internetu i tako dalje, njezin dokaz ima vrlo praktično značenje. A ovdje se ima čime platiti milijun.

Yang-Millsove jednadžbe

Američki fizičari Chen-Ning Franklin Yang i Robert L. Mills (1927.-1999.) sastavili su 1954. godine svoje kvantne jednadžbe, temeljene na najopćenitijim idejama o simetriji elementarnih čestica. Unatoč formalnosti pristupa, jednadžbe savršeno opisuju gotovo sve poznate vrste interakcija - jake, slabe i elektromagnetske. Pomoću jednadžbi čak je predviđeno otkriće novih čestica, koje su kasnije i stvarno pronađene u eksperimentima provedenim u najvećim svjetskim laboratorijima - Brookhaven, Stanford i CERN. Ali u isto vrijeme, još uvijek je nejasno kako oni rade i, općenito, jesu li toliko istiniti. Od svih navedenih jednadžbi, ove su najsloženije, pa ih nećemo iznositi. Ali ako vam pet milijuna koje možete dobiti za rješavanje prethodnih pet problema nije dovoljno, nitko vam neće zabraniti da pokušate riješiti i ovaj. Usudite se i naći ćete.

Vijesti o partnerima

Sedam problema tisućljeća

Predložak 1. Cookov problem (formuliran 1971.)
Recimo, kada ste u velikom društvu, želite biti sigurni da je i vaš prijatelj tamo. Ako vam kažu da on sjedi u kutu, dovoljan vam je djelić sekunde da bacite pogled i uvjerite se u istinitost informacije. Bez ove informacije, bit ćete prisiljeni hodati po cijeloj sobi, gledajući goste. To sugerira da rješavanje problema često traje dulje od provjere točnosti rješenja.
Stephen Cook formulirao je problem: može li provjera točnosti rješenja problema trajati dulje od dobivanja samog rješenja, bez obzira na algoritam provjere. Ovaj problem je jedan od neriješenih problema logike i informatike. Njegovo rješenje moglo bi revolucionirati osnove kriptografije koja se koristi u prijenosu i pohrani podataka.

2. Riemannova hipoteza (formulirana 1859.)
Neki cijeli brojevi ne mogu se izraziti kao umnožak dva manja cijela broja, kao što su 2, 3, 5, 7 itd. Takvi se brojevi nazivaju prostim brojevima i igraju važnu ulogu u čistoj matematici i njezinim primjenama. Distribucija prostih brojeva među svim prirodnim brojevima ne slijedi nikakav obrazac. Međutim, njemački matematičar Riemann iznio je pretpostavku u vezi sa svojstvima niza prostih brojeva. Ako se Riemannova hipoteza dokaže, to će dovesti do revolucionarne promjene u našem znanju o enkripciji i do proboja bez presedana u internetskoj sigurnosti.

3. Hipoteza Bircha i Swinnerton-Dyera (formulirana 1960.)
Povezano s opisom skupa rješenja nekih algebarskih jednadžbi u nekoliko varijabli s cjelobrojnim koeficijentima. Primjer algebarske jednadžbe je jednadžba x2 + y2 = z2. Euklid je dao potpuni opis rješenja ove jednadžbe, ali za složenije jednadžbe dobivanje rješenja postaje izuzetno teško.

4. Hodgeova hipoteza (formulirana 1941.)
U 20. stoljeću matematičari su otkrili moćnu metodu za proučavanje oblika složenih objekata. Glavna ideja je koristiti jednostavne "cigle" umjesto samog objekta, koje su zalijepljene zajedno i tvore njegovu sličnost. Hodgeova hipoteza povezana je s nekim pretpostavkama o svojstvima takvih “cigli” i predmeta.

5. Navier - Stokesove jednadžbe (formulirane 1822.)
Ako plovite u čamcu po jezeru, nastat će valovi, a ako letite u zrakoplovu, u zraku će nastati turbulentna strujanja. Pretpostavlja se da su ti i drugi fenomeni opisani jednadžbama poznatim kao Navier-Stokesove jednadžbe. Rješenja tih jednadžbi su nepoznata, a ne zna se ni kako ih riješiti. Potrebno je pokazati da rješenje postoji i da je dovoljno glatka funkcija. Rješavanjem ovog problema bitno će se promijeniti metode provođenja hidro- i aerodinamičkih proračuna.

6. Poincaréov problem (formuliran 1904.)
Ako gumicu nategnete preko jabuke, možete ju polaganim pomicanjem trake bez podizanja s površine stisnuti do točke. S druge strane, ako je ista gumica prikladno rastegnuta oko krafne, ne postoji način da se traka stisne do točke bez poderanja trake ili lomljenja krafne. Kažu da je površina jabuke jednostavno spojena, ali površina krafne nije. Pokazalo se da je toliko teško dokazati da je samo kugla jednostavno povezana da matematičari još uvijek traže odgovor.

7. Yang-Millsove jednadžbe (formulirane 1954.)
Jednadžbe kvantne fizike opisuju svijet elementarnih čestica. Fizičari Young i Mills, otkrivši vezu između geometrije i fizike čestica, napisali su svoje jednadžbe. Tako su pronašli način da objedine teorije elektromagnetskih, slabih i jakih međudjelovanja. Yang-Millsove jednadžbe implicirale su postojanje čestica koje su zapravo promatrane u laboratorijima diljem svijeta, pa Yang-Millsovu teoriju prihvaća većina fizičara unatoč činjenici da u okviru te teorije još uvijek nije moguće predvidjeti mase elementarnih čestica.

Zadnje ažuriranje: 05/10/2019 02:40 +0300

Čast da bude "prvi" NP-kompletan problem pripada problemu prepoznavanja iz Booleove logike, problemu koji se obično naziva SATISFACTION (skraćeno SATISFACTION). Pojmovi koji se koriste za opisivanje definirani su kako slijedi.

Neka je U = (u 1, u 2, ..., um) skup Booleovih varijabli. Pod skupom istinitosnih vrijednosti na skupu U podrazumijevamo funkciju t: U→(T, F). Ako je t(u) = T, tada ćemo reći da u uzima vrijednost "točno" u odnosu na t; ako je t(u) = F, tada ćemo reći da ima vrijednost "false". Ako je u varijabla iz U, tada se u i i nazivaju literali iz U. Literal i uzima vrijednost "točno" u odnosu na t ako i samo ako varijabla i uzima vrijednost "istinito" u odnosu na t; literal i daje vrijednost true ako i samo ako varijabla " daje vrijednost false."

Disjunkcija nad U je skup literala nad U, na primjer (u 1 , u 3 , u 8 ). Predstavlja disjunkciju ovih literala i kaže se da je zadovoljen za određeni skup istinitih vrijednosti ako i samo ako, za razmatrani skup istinitih vrijednosti, barem jedan od njegovih članova ocijeni kao "točno". U našem primjeru, disjunkcija će biti zadovoljena u odnosu na t, osim ako se istovremeno ne pokaže da je t(u 1) = F, t(u 3) = T, t(u 8) = F. Skup C disjunkcija preko U se naziva zadovoljavajućim ako i samo u slučaju da postoji određeni skup istinitih vrijednosti na skupu U takav da su sve disjunkcije iz C istovremeno zadovoljene. Takav skup istinitih vrijednosti naziva se ispunjavajućim skupom istinitih vrijednosti za C. Problem ZADOVOLJSTVA je formuliran na sljedeći način:

IZVODIVOST

STANJE. Zadan je skup varijabli U i skup C disjunkcija nad U.

PITANJE. Postoji li zadovoljavajući skup istinitih vrijednosti za C?

Na primjer, neka je U = (u 1 , u 2 ) i C = ((u 1 , u 2 ), (u 1 , u 2 )). Ovo je individualni zadatak iz VEP-a čiji je odgovor potvrdan. Zadatak istinitih vrijednosti definiran je na sljedeći način: t(u 1) = t(u 2) = T. S druge strane, zamjena C s C" = ((u 1, u 2), (u 1, u 2), (u 1)), dobivamo primjer pojedinačnog zadatka čiji je odgovor “ne”, budući da je C nemoguće. Sada možemo formulirati Cookov temeljni teorem.

Teorem 2.2 (Cookov teorem). Zadatak je IZVEDIVN.P.- izvršiti zadatak.

Dokaz. Lako je vidjeti da VYP leži u klasi NP. Kako bi riješio ovaj problem, nedeterministički algoritam samo treba specificirati skup istinitih vrijednosti na izvornom skupu varijabli i provjeriti ispunjava li taj skup vrijednosti sve disjunkcije iz originalnog skupa C. Sve je to jednostavno učiniti (na nedeterministički način) u polinomijalnom vremenu. Dakle, prvi zahtjev koji moraju zadovoljiti NP-potpuni problemi je zadovoljen.

Da bismo provjerili ispunjenje drugog zahtjeva, vratimo se na razinu jezika, tj. na prikaz VYP u jeziku Lvyp = L[VYP, e] za neku razumnu shemu kodiranja e da za sve jezike L e NP vrijedi relacija L ∞ Lvyp. Različiti NP jezici mogu biti vrlo različiti; broj ovih jezika je beskonačan, tako da je nemoguće dati poseban sažetak za svaki od njih. Međutim, svaki jezik iz NP može se predstaviti u standardnom obliku, naime pomoću NDMT programa koji radi u polinomijalnom vremenu i prepoznaje ovaj jezik.

Ovo predstavljanje omogućuje rad s općim NDMT programom, čije je vrijeme rada polinom, i dobivanje opće svodivosti jezika koji ovaj program prepoznaje na Lvyp ako je ova opća svodivost specijalizirana za određeni NDMT program M prepoznaje Lm, tada će se željena polinomska redukcija Lm dobiti na Lissue Stoga će, u biti, za sve L ε NP biti prikazan opći dokaz da je L ∞ Lout.

Prvo, razmotrite proizvoljni NDMT program M s polinomnim vremenom izvođenja, koji ima komponente G, Σ, b, Q, q 0 , q y , q n , δ i prepoznaje jezik L = L M . Nadalje, neka je p(n) polinom s cjelobrojnim koeficijentima koji omeđuju odozgo vremensku složenost T m (n). (Bez gubitka općenitosti, možemo pretpostaviti da je p(n) ≥ n za sve n ε Z+.) Funkcija f L koja provodi opću reducibilnost bit će opisana u terminima M, G, Σ, b, Q, q 0, q Y, q n, δ i r.

Pogodno je razmišljati o f L kao preslikavanju skupa riječi u abecedi 2 na pojedinačne probleme iz VEP-a, radije nego na riječi u abecedi S koje kodiraju probleme iz VVP-a, budući da se detalji povezani s kodiranjem mogu lako se popunjava. Dakle, funkcija f l će imati svojstvo da za sve x ε Σ* članstvo x ε L postoji ako i samo ako za skup disjunkcija f l (x) postoji zadovoljavajući skup istinitih vrijednosti. Ključ za konstruiranje funkcije f L je korištenje nekog skupa disjunkcija za pisanje izjave da je x prihvaćen od strane NDMT programa M, tj. izjave x ε L.

Ako je ulazna riječ x ε Σ* prihvaćena od strane programa M, tada za x postoji računanje primanja programa M tako da su broj koraka u fazi provjere i broj simbola u riječi pogađanja ograničeni s p(n ), gdje je n = |x|. U takvom izračunu sudjelovat će samo ćelije s brojevima od -p(n) do p(n)+1. To proizlazi iz činjenice da glava za čitanje/pisanje počinje raditi u ćeliji broj 1 i pri svakom koraku ne pomiče se za više od 1 ćelije. Izračun provjere u potpunosti je određen specificiranjem u svakom trenutku vremena sadržaja ćelija s navedenim brojevima, unutarnjeg stanja i položaja glave za čitanje/pisanje. Nadalje, budući da nema više od p(n) koraka u izračunu verifikacije, potrebno je uzeti u obzir najviše p(n)+1 vremensku točku. To omogućuje da se takav izračun potpuno opiše korištenjem polinomski ograničenog broja Booleovih varijabli i određenog skupa istinitih vrijednosti na njihovom skupu.

Skup varijabli U uključenih u opis funkcije f L namijenjen je posebno za ove svrhe. Prenumerirajmo elemente skupova Q i G na sljedeći način: Q: q 0, q 1 = q y, q 2 = q N, q s, ..., q r, gdje je r = |Q|; G: s 0 = b, s 1 s 2, ..., s v, gdje je v=|G| - 1. Tri vrste varijabli bit će uključene u daljnje zaključivanje, od kojih je svaka dobila određeno značenje prema sl. 2.7. U ovom slučaju izraz "u trenutku i" služi kao kratica za točan izraz "nakon izvođenja j-ro koraka verifikacijskog izračuna."

Izračun programa M očito inducira skup istinitih vrijednosti na skupu ovih varijabli, ako prihvatimo dogovor da kada izračun završi prije vremena p(n), konfiguracija ostaje nepromijenjena cijelo vrijeme nakon zaustavljanja, tj. konačno stanje, položaj glave i snimanje na vrpcu. U trenutku nula, unos trake sastoji se od ulazne riječi x, smještene u ćelijama označenim brojevima od 1 do n, i pogađajuće riječi w u ćelijama označenim brojevima -1 do |w|, sa svim ostalim ćelijama praznima.

S druge strane, proizvoljan skup istinitih vrijednosti za ove varijable ne mora nužno odgovarati nijednom proračunu, a još manje onom koji prima. S obzirom na proizvoljan skup vrijednosti istine za varijable u određenoj ćeliji, mogli bi

riža. 2.7. Varijable disjunkcijskog skupasp(x) i značenje koje im se pridaje

Ako je nekoliko različitih znakova upisano istovremeno, stroj bi mogao biti u nekoliko različitih stanja u isto vrijeme, a glava za čitanje/pisanje mogla bi istovremeno vidjeti bilo koji podskup ćelija numeriranih od -p(n) do p(n)+1. Opis funkcije f L provodi se konstruiranjem takvog skupa disjunkcija koje sadrže navedene varijable tako da će skup istinitih vrijednosti biti ispunjen ako i samo ako je taj skup istinitih vrijednosti induciran nekim primajućim izračunom na ulazu x, a faza provjere ovog izračuna se izvodi u najviše p (n) koraka i pogađačka riječ ima duljinu ne veću od p(n). Tako dobivamo implikacije:

x ε L ↔ na ulazu x nalazi se prijemni izračun programa M

↔ na ulazu x nalazi se prijemni izračun programa M, čiji broj koraka ne prelazi p(n), a pogađačka riječ w ima duljinu jednaku p(n).

↔ postoji zadatak koji izvršava zadatak istinitih vrijednosti za skup disjunkcija problema f l (x).

To će značiti da f l zadovoljava jedan od dva uvjeta potrebna u definiciji reducibilnosti polinoma. Drugi uvjet, da fl mora biti izračunljiv u polinomnom vremenu, može se lako provjeriti kada se fl opiše. bit će završeno.

Disjunkcije pojedinačnog problema f i (x) mogu se podijeliti u 6 skupina, od kojih će svaka nametnuti ograničenje neke vrste na bilo koji zadovoljavajući skup istinitih vrijednosti. Ove grupe prikazane su na sl. 2.8.

Riža. 2.8.Grupe disjunkcija zaf L (x) i ograničenja koja nameću ispunjavajućem skupu istinitih vrijednosti.

Lako je vidjeti da ako svih 6 grupa disjunkcija stvarno postižu svoje predviđene ciljeve, tada se izvršavajući skup vrijednosti istine mora podudarati sa željenim računanjem primanja na ulazu x. Jedino što preostaje jest naznačiti način konstruiranja skupina disjunkcija koje ostvaruju te ciljeve.

Grupa G 1 sastoji se od sljedećih disjunkcija:

(Q, Q, .... Q(i, r]), 0

Prvi p(n)+1 od ovih disjunkcija može se izvršiti istovremeno ako i samo ako je u svakom trenutku vremena i program M u barem jednom stanju. Preostale (p(n)+1) (r + 1) (r/2) disjunkcije mogu se izvršiti istovremeno ako i samo ako ni u jednom trenutku i program M nije u više od jednog stanja. Time G1 ispunjava svoju svrhu.

Grupe G 2 i G 3 konstruirane su na sličan način, ali su grupe G 4 i G 5 vrlo jednostavne, svaka uključuje disjunkcije koje se sastoje od samo jednog literala. Na sl. 2.9 pruža potpuni opis prvih pet skupina disjunkcija. Imajte na umu da su i broj disjunkcija u tim skupinama i maksimalni broj literala uključenih u svaku disjunkciju ograničeni određenim polinomom u n (budući da su r i v konstante koje su određene M i, stoga, jezikom L).

Riža. 2.9.Prvih 5 skupina disjunkcija za f L (X).

Opis posljednje skupine disjunkcija je nešto kompliciraniji - G 6, koji jamči da je svaka sljedeća konfiguracija stroja dobivena iz prethodne kao rezultat primjene jedne naredbe M programa. Ova skupina se sastoji od dvije podskupine disjunkcije.

Prva podskupina jamči da ako glava za čitanje/pisanje u trenutku i ne gleda ćeliju broj j, tada se znak u ćeliji broj j od trenutka i do trenutka i + 1 neće promijeniti. Disjunkcije ove podgrupe imaju oblik

Proizvoljno fiksirajmo trenutak vremena t, ćeliju s brojem j i simbol s l Ako u trenutku vremena i glava za čitanje/pisanje ne gleda u ćeliju s brojem j iu toj ćeliji u trenutku vremena i simbol j je napisan, au trenutku vremena i + 1 već postoji ne, tada gornja disjunkcija neće biti zadovoljena (inače će biti zadovoljena). Dakle, 2(p(n)+ l) 2 (v + 1) disjunkcija ove grupe ispunjava svoju svrhu.

Druga podskupina disjunkcija iz skupine G 6 jamči da se restrukturiranje jedne strojne konfiguracije u sljedeću događa prema prijelaznoj funkciji δ programa M. Za svaka četiri

(i, j, k, l), 0 ≤ i< p(n), -р(n) ≤ j ≤ р(n) + 1, 0 ≤ k ≤ r и 0 ≤ l ≤ v,

ova podskupina sadrži sljedeće tri disjunkcije:

gdje su vrijednosti ∆, k" i l" definirane na sljedeći način:

ako je q k ε Q\(q y , q N ), tada je δ(q k , s l) = (q k ` , s l ` , ∆),

a ako je q k ε (q Y , q N ), onda je ∆= 0, k" = k i l" = l.

Nije teško vidjeti (iako može potrajati nekoliko minuta razmišljanja) da ovih 6(p(n))(p(n) + 1)(r+1)(v+1) disjunkcija osigurava potrebno ograničenje na ispunjavajući skup vrijednosti istine.

Dakle, pokazali smo kako konstruirati grupe disjunkcija G 1 -G 6 koje ispunjavaju svoju svrhu. Ako x ε L, tada program M na ulazu x ima primateljski izračun duljine ne veći od p(n), a ovaj izračun daje, za danu interpretaciju varijabli, skup istinitih vrijednosti koje će zadovoljiti sve disjunkcije iz C=G 1 UG 2 UG 3 UG 4 UG 5 UG 6 . Suprotno tome, skup disjunkcija C konstruiran je tako da svatko tko izvršava skup istinitih vrijednosti za C mora odgovarati nekom primajućem izračunu programa M na ulazu x. Slijedi da za f l (x) postoji zadovoljavajući skup istinitih vrijednosti ako i samo ako je x ε L.

Sada ostaje pokazati da se za bilo koji fiksni jezik L može konstruirati pojedinačni problem f l (x) u vremenu ograničenom polinomom od n = |x|. Ako je dan jezik L, tada možete izabrati neki NDMT program M koji prepoznaje L u vremenu ograničenom polinomom p (nema potrebe da se sam nedeterministički program nalazi u polinomnom vremenu, jer je potrebno samo pokazati da preslikavanje f l postoji). Ako postoji određeni NDMT program M i polinom p, tada konstruiranje skupa varijabli U i skupa disjunkcija C zahtijeva malo više posla od popunjavanja svih pozicija u standardnoj (iako prilično složenoj) formuli. Polinomska ograničenost ovog izračuna bit će jasna ako pokažemo da je duljina ograničena gore polinomom u n, gdje je duljina[I], kao što je navedeno u Odjeljku. 2.1, karakterizira duljinu riječi koja kodira pojedinačni zadatak I, pod nekom razumnom shemom kodiranja.

Kao “razumnu” funkciju duljine za VEP problem, možemo, na primjer, uzeti |U||S|. Nijedna disjunkcija ne može sadržavati više od 2|U| literala (budući da je ukupan broj literala 2|U|), a broj znakova potrebnih za opisivanje svakog pojedinačnog literala nije veći od log|U|, ali se ta vrijednost može zanemariti jer daje polinomski doprinos ukupnom duljina problema. Budući da su r i v unaprijed fiksni, mogu povećati |U| i |C| konstantan broj puta, pa imamo |U| = O(p(n) 2) i |C| = O(p(n)) 2 . Prema tome, Duljina = |U|| C| = O(r(n) 4) i stoga je ograničen polinomom od n, kako se zahtijeva.

Prema tome, transformacija f l može se izračunati algoritmom koji ima polinomsku vremensku složenost (međutim, specifično ograničenje polinoma na složenost ovisit će o L kao i o izboru M i p), iz čega možemo zaključiti da za sve L ε NP funkcija f L je izračunljiva u polinomnom vremenu i preslikava L u OUT (točnije, preslikava L u Lout). Ovo implicira tvrdnju teorema da je VYP NP-kompletan problem.▀

Dokaz rezultata oN.P.- potpunost

3-ZADOVOLJIVOST (3-PROBLEMA)

STANJE. Zadan skup C = (c 1 , c 2 , ..., c m ) disjunkcija na konačnom skupu varijabli U tako da je |c i | = 3, 1 ≤ i ≤ m.

PITANJE. Postoji li skup istinitih vrijednosti na U takav da sve disjunkcije u C vrijede?

TRODIMENZIONALNA KOMBINACIJA (3-C)

STANJE. Zadan je skup M ε W x X x Y, gdje su W, X i Y disjunktni skupovi koji sadrže isti broj elemenata q.

PITANJE. Je li točno da M sadrži trodimenzionalnu kombinaciju, tj. podskup M" ε M, takav da je |M`|=q i nijedna dva različita elementa od M" nemaju jednake koordinate?

VERTIKALNI PREMAZ (VP)

STANJE. Zadani su graf G =(V, E) i prirodni broj K, K ≤ |V|.

PITANJE. Ima li graf G vrh vrhova od najviše K elemenata, tj. podskup V" ε V takav da je |V`| ≤ K i za svaki brid (u, v) ε E barem jedan od vrhova u ili v pripada V`?

KLIKA

STANJE. Zadan je graf G=(V, E) i prirodni broj J ≤ |V|.

PITANJE. Je li točno da G sadrži neku kliku kardinalnosti najmanje J, odnosno podskup V` ε V takav da je |V`| ≥ J i bilo koja dva vrha iz V spojena su bridom iz E?

HAMILTONOV CIKLUS (HC)

STANJE. Zadan je graf G=(V, E).

PITANJE. Je li točno da G sadrži Hamiltonov ciklus, tj. takav niz vrhovi grafa G tako da je n=|V|, (v n ,V 1) ε E i (v i , v i +1 )ε E za sve i, 1≤ i ≤ n.

RAZBIJANJE

STANJE. Dan je konačan skup A i “težina” s(a) ε Z+ za svaki a ε A.

PITANJE. Postoji li podskup A" ε A takav da

3-izvedivost

Problem 3-SATITIZABILITY je jednostavno ograničena verzija problema SATISFACTION u kojem svaki pojedinačni problem ima točno tri literala u svakoj klauzuli.) Zbog svoje jednostavne strukture, ovaj problem se najčešće koristi za dokazivanje rezultata NP-potpunosti.

Teorem 3.1. Problem 3-SAITIZABILNOST jeN.P.- puna.

Dokaz. Lako je vidjeti da je 3-OUT ε NP. To proizlazi iz činjenice da nedeterministički algoritam treba pogoditi samo skup vrijednosti istinitosti problemskih varijabli i provjeriti u polinomnom vremenu hoće li, s takvim skupom vrijednosti istinitosti, sve zadane triliteralne disjunkcije biti zadovoljene.

Svedimo problem VYP na problem 3-VYP. Neka je U = (u 1 , u 2 , …, u n ) skup varijabli i C = (c 1 , c 2 , ..., c m ) proizvoljan skup disjunkcija koji definira proizvoljan pojedinačni problem iz VO. Konstruirajmo skup C" triliteralnih disjunkcija na nekom skupu varijabli U" tako da je C" zadovoljeno ako i samo ako je C zadovoljeno.

Skup C" će biti konstruiran zamjenom svake pojedinačne disjunkcije c j ε s "ekvivalentnim" skupom C` j triliteralnih disjunkcija na skupu U izvornih varijabli i skupu U" j nekih dodatnih varijabli, te varijabli iz U" j će se koristiti samo u disjunkciji od C` j. Drugim riječima,

Dakle, samo trebate pokazati kako na temelju cj možete konstruirati C` j i U` j. Neka je c j zadan skupom (z 1, z 2, ..., z k), gdje su z i, literali na skupu U. Metoda formiranja C` j i U" j ovisi o vrijednosti k.

Da bismo dokazali da ovdje doista postoji reducibilnost, potrebno je pokazati da je skup disjunkcija C" zadovoljen ako i samo ako zadovoljimo skup disjunkcija C. Pretpostavimo prvo da je t: → (T, F) skup istinite vrijednosti, izvršavajući C. Pokažimo da se t može proširiti na skup istinitih vrijednosti t": U" → (T,P) koji izvršava C". Budući da su varijable u skupu U"\U podijeljene u skupine U` j i budući da su varijable u svakoj skupini U` j uključene samo u disjunkcije koje pripadaju C` j, tada je dovoljno pokazati kako se t može proširiti svakom skupu U` j posebno, au svakom slučaju potrebno je provjeriti jesu li sve disjunkcije zadovoljene u odgovarajućem skupu C` j.

To se može učiniti na sljedeći način. Ako su U` j konstruirani, kao u slučaju 1 ili 2, tada su disjunkcije iz C` j već izvedene pomoću t, tako da se t može proizvoljno proširiti na U` j, na primjer, ako stavimo t"(y) = T za sve y ε U" j . Ako je U" j konstruiran kao u slučaju 3, tada je U` j prazan i jedina disjunkcija u C` j već je zadovoljena t. Ostaje samo slučaj 4, koji odgovara disjunkciji (z 1 , z 2 , .. .. ., z k ) iz C, i k > 3. Budući da je t ispunjavajući skup istinitih vrijednosti za C, tada postoji cijeli broj l tako da z l u t ima vrijednost true Ako je l = 1 ili 2, tada postavljamo t"(y i j) =F, 1 ≤ i ≤ k - 3. Ako je l = k - 1 ili k, tada postavljamo t"(y i j) = F, 1 ≤ .i ≤ k - 3. Inače postavljamo t"(y ij) = T za 1 ≤ i ≤ l -2 i t" (yij) = F za l-1 ≤ i ≤ k -3. Lako je provjeriti da je takav skup istinitosti vrijednosti ​​će osigurati da su sve disjunkcije u C`j zadovoljene, tako da t` ispunjava sve disjunkcije iz C". Obrnuto, ako je t" neki zadovoljavajući skup istinitih vrijednosti za C", tada je lako provjeriti da ograničenje t" na varijable iz U mora biti zadovoljavajući skup istinitih vrijednosti za C. Dakle, C" je zadovoljeno ako i samo ako smo zadovoljili C .

Kako bi se potvrdilo da je ova reducibilnost polinomna, dovoljno je primijetiti da je broj triliteralnih disjunkcija u C" ograničen polinomom u itd. Posljedično, veličina pojedinačnog 3-VYP problema ograničena je odozgo određenim polinom od veličine odgovarajućeg VYP problema, a budući da su sve detaljne konstrukcije reducibilnosti očite, čitatelju neće biti teško provjeriti je li ta reducibilnost polinomna.▀

Ograničena struktura problema 3-RIN čini ga mnogo korisnijim u dokazivanju rezultata NP-potpunosti u usporedbi s problemom RIN. Bilo koji dokaz temeljen na ER problemu (osim ovog upravo navedenog) može se lako pretvoriti u dokaz temeljen na 3-ER, čak i bez mijenjanja funkcije koja izvodi reducibilnost. U stvari, dodatni uvjet da sve disjunkcije imaju istu duljinu često može pojednostaviti reducibilnost koju treba konstruirati, a time i olakšati pronalaženje. Štoviše, vrlo kratka duljina disjunkcija dopušta korištenje reducibilnosti koje se uopće ne mogu konstruirati za pojedinačne probleme s disjunkcijama veće duljine. Ovo sugerira da bi bilo još bolje kada bi se analogni problem 2-SATIFIABILITY (svaka disjunkcija sadrži točno dva literala) mogao pokazati kao NP-kompletan. Međutim, 2-VYP se može riješiti metodom "rezolucije" u vremenu ograničenom polinomom umnoška broja disjunkcija i broja varijabli danog pojedinačnog problema (vidi također), i stoga pripada klasa P.

Da biste to učinili, trebate samo sjesti, razmisliti i riješiti jedan od matematičkih “problema tisućljeća”.

7X7

Od prošlog stoljeća broj takvih problema smanjio se gotovo četiri puta. Kad je poznat njemački matematičar David Gilbert na samom početku 20. stoljeća govorio je na međunarodnom matematičkom kongresu u Parizu; njegov popis matematičkih i logičkih problema koje je trebalo riješiti u sljedećih stotinu godina uključivao je 23 stavke. Plus još tri problema s kojima je govor započeo, a koji, već spomenuti, nisu uvršteni u glavni popis. Gilbertu su se činili tako očiglednima.

Ukupno je do kraja stoljeća u potpunosti riješeno 20 problema. Prvi koji je predstavljen i posljednji riješen bio je Fermatov posljednji teorem. Dva su preostala problema djelomično riješena, dva su još uvijek otvorena, jedan - o matematičkom opisu fizikalnih aksioma - prepoznat je kao nematematički, a jedan - o ravnoj liniji, kao najkraćoj vezi dviju točaka - također je proglašen. nejasno, zbog čega je bilo nemoguće razumjeti je li riješena ili ne. Ono što je zanimljivo: svih 20 problema riješeno je potpuno besplatno. Rješavanje Gilbertovih problema nije podrazumijevalo nikakvu nagradu osim vječne znanstvene slave i dubokog znanstvenog zadovoljstva.

Novi popis, sastavljen početkom ovog stoljeća, svjetskih matematičkih problema broji samo sedam. Za razliku od Gilbertove, trenutni popis, nazvan Problemi milenijske nagrade, dodjeljuje se za rješavanje svakog od njih. Matematički institut Clay(Cambridge, Massachusetts, SAD) dodijeljena je nagrada od milijun dolara, naprotiv: odabrano je točno sedam problema prema broju milijuna izdvojenih za njihovo rješavanje.

Za referencu

Ako preko lopte nategnete elastičnu traku, pa ju postupnim zatezanjem, a da je nigdje ne pokidate ili otkinete s površine, skupite u jednu točku. Prevučete li takvu vrpcu preko krafne, po vanjskoj ili unutarnjoj strani, isti trik vam više neće uspjeti. Vrlo nepristojno "Poincaré problem" može se formulirati na sljedeći način: ako je moguće povući bilo koju proizvoljno rastegnutu elastičnu traku s predmeta, poput lopte, a da je ne otkinete s površine ili ne potrgate, tada taj predmet nema rupa. Ova izjava je nazvana "problemom" jer je nitko nije mogao dokazati, budući da ju je postavio francuski matematičar Jules Henri Poincaré 1904. godine. U međuvremenu, iako je još uvijek teško pronaći konkretnu primjenu za ovu tvrdnju, ona je vrlo važna za teorijsku matematiku, posebno za topologiju (grana matematike koja proučava prostorne transformacije). Sve dok nije bilo konkretnih dokaza, trebalo je biti vrlo oprezan s izjavom: što ako je Poincaré bio u zabludi? Sada mu možete sa sigurnošću vjerovati.

Antiteza

Prvi Clay Million dodijeljen je 18. ožujka 2010 star 43 godine Ruski matematičar, zaposlenik peterburške podružnice Matematičkog instituta Steklov, Grigorij Perelman, koji je riješio takozvani "Poincareov problem".

Vjeruje se da je jedan od razloga zašto ovaj sanktpeterburški matematičar, kojeg je britanski The Daily Telegraph smjestio na 9. mjesto na popisu stotinu živućih genija, odbija komunicirati s ruskim novinarima njihova očita familijarnost i nekompetentnost. I istina je. Često se u člancima Grigorija Jakovljevića naziva čak i ne Grigorijem, već Grišom, a njegovog oca nazivaju velikim popularizatorom znanosti. Pritom se autori članaka niti ne trude otvoriti enciklopediju i saznati da je Jakov Isidorovič umro od gladi u opkoljenom Lenjingradu 1942. godine, a Grigorij Jakovljevič rođen je tek 1966., 24 godine kasnije.

Još u školi dječak je pokazao značajne sposobnosti, ne samo u matematici, već iu glazbi. Osim uobičajene, išao je i u glazbenu školu, gdje je učio violinu, te u matematički centar u Palači pionira. Već u srednjoj školi prešao je u specijaliziranu fizikalno-matematičku školu koju je završio sa srebrnom medaljom. Loša fizička priprema spriječila ga je da dobije zlatnu medalju: koliko god se trudio, budući matematički genij nije uspio proći GTO standarde.

Nakon škole, on se, kao dobitnik medalje, suočio s teškim izborom gdje će ići bez ispita - na Konzervatorij ili na Matematiku i mehaniku Lenjingradskog državnog sveučilišta. Pobijedila je strast prema matematici. Diplomirao je na sveučilištu s odličnim uspjehom. Godine 1990. Grigorij Jakovljevič obranio je doktorsku disertaciju i otišao raditi u SAD, odakle se vratio šest godina kasnije. Istodobno mu je dodijeljena nagrada Europskog matematičkog društva za mlade matematičare, ali ju je Grigorij Jakovlevič odbio primiti. Radio je kao vodeći istraživač u laboratoriju matematičke fizike peterburške podružnice Matematičkog instituta nazvanog po. V. A. Steklova RAS (POMI), ali je 2005. dao ostavku i gotovo potpuno prekinuo kontakte s vanjskim svijetom. A godinu dana kasnije, za rješavanje jednog od "nagradnih problema", naime "Poincaréovog problema", dobio je glavnu nagradu među matematičarima - Fieldsovu medalju (novčani ekvivalent - 15.000 kanadskih dolara, po današnjem tečaju - 432.000 rubalja) .

Ali Perelman je također odbio Fieldsovu medalju. Dvije su godine stručnjaci provjeravali ispravnost njegove odluke. I tek 2010. akademsko vijeće Instituta Clay objavilo je da nisu pronađene pogreške ili prijevare, a ruski matematičar mogao je doći po novac. Međutim, Perelman je najavio da neće letjeti u Cambridge. Odbio je i druge opcije za transfer milijun dolara. U jednom od svojih nekoliko intervjua ovako je objasnio svoj postupak:

- Odbio sam. Znate, imao sam puno razloga u oba smjera. Zato mi je trebalo toliko vremena da se odlučim. Ukratko, glavni razlog je neslaganje s organiziranom matematičkom zajednicom. Ne sviđaju mi ​​se njihove odluke, mislim da su nepravedne. Smatram da doprinos američkog matematičara Hamiltona rješavanju ovog problema nije ništa manji od mog.

A nedavno, u drugom intervjuu, Grigory Yakovlevich je priznao:

“Naučio sam izračunati praznine, a zajedno s kolegama učimo mehanizme popunjavanja društvenih i ekonomskih “praznina”. Posvuda su praznine. Mogu se izračunati, a to daje velike mogućnosti... Znam kako kontrolirati svemir. A reci mi - zašto da trčim za milijun?!

Što je ostalo

U svakom slučaju, milijun je već nestao. No, ostalo ih je još šest. Za što ih još možete nabaviti?

Birchova i Swinerton-Dyerova pretpostavka

“Kamenom mudraca” matematike možemo nazvati jednadžbe oblika x n +y n +z n +.....=t n. Najjednostavniju stvar, x 2 +y 2 =z 2 (na primjer, 3 2 +4 2 =5 2), u potpunosti je istražio Euklid 300 godina prije Kristova rođenja. Najpoznatija od tih jednadžbi postala je osnova za Fermatov teorem. A jedno od najvećih rješenja (u eri prije računala) predložio je Euler 1769. godine. Uspio je konstruirati sljedeću jednakost: 2 682 4404 + 15 365 6394 + 18 796 7604 = 20 615 6734. Za takve jednadžbe ne postoji univerzalna metoda izračuna. Međutim, poznato je da svaki od njih može imati konačan ili beskonačan broj rješenja. Matematičari Birch i Swinerton-Dyer 1960. godine stvorili su metodu kojom se svaka takva jednadžba može svesti na jednostavniju, nazvanu zeta funkcija. Prema njihovoj eksperimentalno izvedenoj, ali ne i teorijski dokazanoj pretpostavci, ako je ova funkcija u točki 1 jednaka 0, tada će broj rješenja željene jednadžbe biti beskonačan. U suprotnom, ili ih uopće neće biti, kao što je slučaj s Fermatovim teoremom, ili će ih biti ograničen broj. Do sada nitko nije uspio dokazati ili opovrgnuti ovu tvrdnju.

Hodgeova pretpostavka

Predmet je teže proučavati što je njegova struktura složenija. Stoga ga matematičari obično prvo pokušavaju rastaviti na jednostavnije objekte s kojima je, kao što je jasno, lakše raditi. Problem je u tome što nije uvijek moguće jednostavno rastaviti objekt na njegove komponente. Ponekad se u ovom slučaju pojavljuju novi dijelovi, nepoznato je odakle su došli i nije jasno što predstavljaju. Ili, naprotiv, detaljnije istraživanje otkriva da neki detalji očito nedostaju. Jednostavno, promatrajući same cigle, ne možemo zamisliti kakva je kuća napravljena od njih, kako izgleda i po kojim se pravilima gradi. Da biste to učinili, morate barem proučiti prazan prostor prostorija između njih. Profesor s Cambridgea William Hodge u svojim je spisima 1941. opisao uvjete pod kojima, kako mu se čini, ne mogu nastati takvi neshvatljivi "suvišni" dijelovi i u kojima se bilo koje geometrijsko tijelo može proučavati kao algebarska jednadžba, stvarajući njegov matematički model. Znanstvenici već 70 godina ne mogu dokazati njegovu pretpostavku niti je opovrgnuti.

Navier-Stokesove jednadžbe

Kad brodom plovite po jezeru, iz njega se šire valovi. Prateći avion koji leti ili jureći automobil nastaju turbulentna strujanja - valoviti zračni vrtlozi. Svi ovi fenomeni opisani su Navier-Stokesovim jednadžbama stvorenim davne 1822. godine. Unatoč činjenici da su jednadžbe nastajale dosta dugo, nitko ih još uvijek ne zna riješiti. Štoviše, još nitko ne zna ni postoji li način da ih se uopće riješi. Istodobno, vrlo ih aktivno koriste ne samo matematičari, već i dizajneri zrakoplova, automobila i brodova. Istina, zasad se mogu koristiti samo NT metodom (“znanstvenim bockanjem”): zamjenjujući već poznate vrijednosti brzine, vremena, tlaka, gustoće itd. i provjeravajući odgovaraju li jedna drugoj. Ako netko pronađe metodu rješenja, moći će se koristiti jednadžbe u suprotnom smjeru, računajući sve potrebne parametre iz jednakosti. Ovo će učiniti aerodinamička ispitivanja nepotrebnima. Međutim, matematičar će dobiti nagradu čak i ako dokaže da ne postoji metoda rješenja.

Problem provjere odluke (problem Cook-Lewin)

Ako čovjek dobije zadatak da pronađe blago zakopano tamo u prošlom stoljeću u šumi, na potragu može potrošiti godinu, dvije, desetljeće, pa čak i cijeli život. Sve se odvija mnogo brže kada mu kažu: “Blago je zakopano ispod jedine jasike u šumi. Idi i provjeri." Ista stvar se događa prilikom rješavanja bilo kojeg problema. Svi dobro razumijemo da provjera rješenja obično traje kraće nego samo rješenje. Razumijemo, ali kako se pokazalo, ne možemo dokazati ovu jednostavnu i naizgled logičnu činjenicu. Stoga, ako uspijete pronaći takav problem, čija će vam provjera ispravnosti rješenja, bez obzira na način provjere, oduzeti više vremena nego samo rješenje - hitno se obratite Institutu Clay i za dvije godine postat ćete vlasnik od milijun dolara. Rješenje “Cookovog problema” formuliranog 1971. godine, prema znanstvenicima, dovest će do prave revolucije u području kriptografije i do pojave sustava šifriranja koji se jednostavno ne mogu probiti. Vrlo grubo: pojavit će se šifre, čija će provjera ispravnosti razbijanja trajati beskrajno dugo.

Riemannova hipoteza

Među cijelom masom brojeva posebno mjesto zauzimaju brojevi koji se ne mogu podijeliti ni na što manje od sebe: 1, 2, 3, 5, 7, 11, 13, 17 i tako dalje. Takvi brojevi se nazivaju "prim" i izuzetno su važni za matematičare. Kako su raspoređeni duž numeričkog niza, to zna samo Bog. Riemann 1859. nije čak ni predložio način kako ih pronaći ili testirati. Jedini način da provjerite je li broj "prost" ili ne je da ga pokušate podijeliti na sve manje i manje brojeve (najveći "prost" do danas pronađen je u kolovozu 2008. i sastoji se od 12.978.189 znamenki). Jednostavno je pronašao metodu kojom se može odrediti najveći broj prostih brojeva koji ne prelaze određeni zadani broj. Do danas su matematičari testirali ovu metodu s trilijun i pol "jednostavnih". Do sada nisu pronađeni kvarovi. Međutim, to uopće ne znači da se metoda neće spotaknuti na prvih jedan i pol bilijun čeka. A budući da se Riemannova hipoteza, koja je na novi popis prenesena s Gilbertove liste, aktivno koristi za izračun sigurnosnih sustava prijenosa podataka - u mobilnim mrežama, na Internetu i tako dalje - njen dokaz ima vrlo praktično značenje. A ovdje se ima čime platiti milijun.

Yang-Millsove jednadžbe

Američki fizičari Zhen-Ning Yang i Robert Mills sastavili su svoje kvantne jednadžbe 1954. godine, promatrajući kretanje elementarnih čestica. Izvedeni gotovo iz čiste intuicije, oni ipak izvanredno opisuju gotovo sve vrste svojih interakcija. Pomoću jednadžbi čak je predviđeno i otkriće novih čestica, koje su kasnije doista i pronašli nuklearni fizičari u najvećim svjetskim laboratorijima – Brookhaven, Stanford i CERN. Istina, korištenjem Yang-Millsove teorije nemoguće je točno predvidjeti masu čestica, međutim, unatoč tome, gotovo svi nuklearni znanstvenici u svijetu pouzdano koriste jednadžbe. Iako je još uvijek nejasno kako djeluju i, općenito, jesu li toliko istiniti. Od svih navedenih jednadžbi, ove su najsloženije, pa ih nećemo iznositi. No, ako vam pet milijuna koje možete dobiti za rješavanje prethodnih pet problema nije dovoljno, nitko vas neće spriječiti da pokušate riješiti i ovaj. Usudite se - i naći ćete.

Ili bismo možda trebali pričekati?

Perelmanovo prezime sada pamti cijeli civilizirani svijet. Ali tko je ovo? Andrew Wiles Znaju samo specijalisti. Ali 1995. godine on je bio taj koji je ispunio stoljetni san matematičara - dokazao je Fermatov posljednji teorem, formuliran davne 1637. godine. Za njegovo rješenje 1908. godine raspisana je i posebna nagrada od 100.000 njemačkih maraka, što je za početak prošlog stoljeća bilo iznimno visoko. Međutim, dva svjetska rata i s njima povezana inflacija prilično su ga srezali. Toliko da je matematičar za svoj rad dobio čisto simboličan iznos, otprilike 15 dolara. Da je Wiles čekao 6-7 godina da objavi svoj dokaz, Fermatov teorem bi definitivno bio uključen u “Probleme milenijske nagrade” i bio bi procijenjen na milijun. I tada bi matematičar postao vrlo bogat. Ili vrlo poznat. Kao Grigorij Perelman.