OpenAI i Anthropic otvorili raspravu o hipotezi ETH
OpenAI je objavio rešenja za tri velika matematička problema, uključujući tvrdnju da je opovrgnuta hipoteza o eksponencijalnom vremenu (ETH), koju su Russell Impagliazzo i Ramamohan Paturi formulisali 1999. Anthropic je nekoliko sati kasnije objavio sopstveno osporavanje ETH-a. U središtu obe objave nalaze se algoritmi za određenu klasu teških logičkih problema, za koje laboratorije tvrde da rade u subeksponencijalnom vremenu.
Šta ETH predstavlja u teoriji složenosti
ETH je važna pretpostavka u računarstvu jer govori da čak i najbrži algoritmi za određene probleme zahtevaju eksponencijalno više vremena kako raste broj promenljivih. Ona pripada širem skupu pitanja oko odnosa P i NP: da li se svaki problem čije se rešenje može brzo proveriti može i brzo rešiti.
Primer je Sudoku. Kada je rešenje dato, njegova ispravnost se može brzo proveriti, ali pronalaženje rešenja može zahtevati mnogo vremena. Slična asimetrija ima značaj i za kriptografiju: posedovanje ključa omogućava čitanje šifrovane poruke, dok bi razbijanje delotvorne šifre bez ključa trebalo da traje predugo da bi bilo korisno.
Ako se tvrdnje laboratorija potvrde, ETH bi bila netačna, a ranije intuicije o tome koliko su teški pojedini NP problemi morale bi da se preispitaju. To samo po sebi ne dokazuje da je P jednako NP. Ryan Williams sa MIT-a ocenjuje da rezultat može povećati uverljivost te mogućnosti, ali ne predstavlja konačan odgovor niti nužno najbolji mogući algoritam.
Provera dokaza i posledice za istraživanja
Williams organizuje odgovor zajednice računarskih naučnika zajedno sa Impagliazzom i Paturijem. Grupa je pozvala zainteresovane istraživače da daju povratne informacije, zatražila javnu objavu dokaza i predložila konferenciju koju bi OpenAI finansirao. Prema Williamsu, u dokazima postoje rutinski delovi, ali i nekoliko neuobičajenih delova koje zajednica treba zajednički da proveri.
Ukoliko se rezultat održi, brojne radove koji su se poslednje decenije oslanjali na ETH trebalo bi ponovo razmotriti. Pitanje nije samo razumevanje novog algoritma, već i utvrđivanje koje teorijske osnove ostaju pouzdane za naredna istraživanja.
Kriptografija nije označena kao neposredno ugrožena
Bolji algoritmi mogu otvoriti pitanje bezbednosti kriptografskih sistema čija zaštita zavisi od određenih veličina ključeva. Williams je zato pitao vođu naučnog tima OpenAI-ja Dana Robertsa da li su provereni mogući efekti na kriptografiju. OpenAI je naveo da je obavio proveru i da je bio razumno uveren da rezultat ne implicira probijanje sistema.
Za organizacije je praktičan zaključak da ovu objavu ne treba tumačiti kao neposrednu promenu bezbednosnog stanja, ali da treba pratiti nezavisnu stručnu proveru. Potvrđena promena ETH-a mogla bi da utiče na istraživačke pretpostavke, procene algoritamskih rizika i dugoročno planiranje bezbednosti.