Zašto računalnim znanstvenicima trebaju magiju 8 loptica poput loptica

Izvorna verzija od ova priča pojavio se u Magazin Quanta.

Postavite pitanje magičnoj 8 kuglica i odgovorit će da, ne, ili nešto neugodno neodlučno. Mi to smatramo dječjom igračkom, ali teorijski računalni znanstvenici koriste sličan alat. Često zamišljaju da se mogu konzultirati s hipotetičkim uređajima zvanim oraci koji mogu odmah i ispravno odgovarati na određena pitanja. Ovi fantastični eksperimenti misao nadahnuli su nove algoritme i pomogli istraživačima da mapiraju krajolik računanja.

Istraživači koji se pozivaju na orace djeluju u podskupini informatike pod nazivom Teorija računalne složenosti. Oni se bave inherentnim poteškoćama problema poput utvrđivanja je li broj glavni ili pronalaženje najkraćeg puta između dvije točke u mreži. Neke su probleme lako riješiti, drugi izgledaju mnogo teže, ali imaju rješenja koja je lako provjeriti, dok su još uvijek jednostavni kvantna računala Ali naizgled teški za obične.

Teoretičari složenosti žele razumjeti jesu li te prividne razlike u poteškoćama temeljne. Postoji li nešto intrinzično teško u određenim problemima ili nismo dovoljno pametni da bismo smislili dobro rješenje? Istraživači se bave takvim pitanjima razvrstavanjem problema u „razredi složenosti”-na primjer, svi jednostavni problemi idu u jednoj klasi, a svi jednostavni problemi idu u drugom-i dokazuju teoreme o odnosima između tih klasa.

Nažalost, pokazalo se da je mapiranje krajolika računalnih poteškoća teško. Dakle, sredinom 1970-ih, neki su istraživači počeli proučavati što će se dogoditi ako se pravila računanja razlikuju. Tu ulaze oraci.

Poput Magic 8 kuglica, oraci su uređaji koji odmah odgovaraju na pitanja ili bez pitanja, a da ne otkrivaju ništa o njihovom unutarnjem djelovanju. Za razliku od Magic 8 kuglica, oni uvijek kažu ili da ili ne, i uvijek su točni – prednost je što su izmišljeni. Osim toga, bilo koji dani Oracle će odgovoriti samo na određenu vrstu pitanja, poput “Je li ovaj broj glavni?”

Što ove izmišljene uređaje čini korisnim za razumijevanje stvarnog svijeta? Ukratko, oni mogu otkriti skrivene veze između različitih složenih klasa.

Uzmite dvije najpoznatije klase složenosti. Postoji klasa problema koje je lako riješiti, a istraživači nazivaju “P” i klasu problema koje je lako provjeriti, a koji istraživači nazivaju “NP”. Jesu li i svi jednostavni problemi s provjeravanjem također lako riješiti? Ako je tako, to bi značilo da bi NP jednak P, a sva šifriranje bilo bi lako puknuti (između ostalih posljedica). Teoretičari složenosti sumnjaju da NP ne izjednačava P, ali to ne mogu dokazati, iako su pokušavali zabiti odnos između dviju klasa za preko 50 godina.

Orkaci su im pomogli da bolje razumiju s čime rade. Istraživači su izmislili orakove koji odgovaraju na pitanja koja pomažu u rješavanju mnogih različitih problema. U svijetu u kojem je svako računalo imalo telefonsku liniju za jedan od tih orarola, sve bi se lako provjeravali problemi također lako riješiti, a P bi izjednačio NP. Ali drugi, manje korisni oraci imaju suprotan učinak. U svijetu naseljenim tim orakovima, P i NP bi se dokazano razlikovao.