Kanal Fireship, ki ga poznajo predvsem programerji, je ta teden posvetil video temi, o kateri se zadnje dni živahno razpravlja v računalniških krogih: nepoimenovan model podjetja OpenAI naj bi napisal algoritem, ki rešuje znameniti problem 3-SAT hitreje, kot pravi dolgoletna domneva. Če trditev drži, je to velik trenutek za teoretično računalništvo.

Kaj je problem 3-SAT in zakaj je domneva pomembna?

Predstavljaj si ogromno uganko z ničlami in enicami, kjer moraš izbrati vrednosti tako, da so izpolnjeni vsi pogoji hkrati. Takšne naloge so v ozadju načrtovanja, preverjanja programske opreme in varnosti. Leta 1999 sta Russell Impagliazzo in Ramamohan Paturi zapisala hipotezo o eksponentnem času (ETH): ta pravi, da se 3-SAT v bistvu ne da rešiti bistveno hitreje od preizkušanja vseh možnosti. Po opisu videa na tej predpostavki sloni več kot 800 objavljenih člankov, saj številni dokazi o »težkosti« drugih problemov izhajajo iz nje.

OpenAI je po poročanjih medijev objavil rokopis z naslovom, ki trdi, da je ta hipoteza napačna, in opisuje algoritem, ki deluje v podeksponentnem času. Poročajo tudi o vzporedni objavi podjetja Anthropic, vendar so vsi ti podatki za zdaj trditve podjetij, ki jih neodvisni strokovnjaki še preverjajo.

Zakaj naslov pravi »kinda« in zakaj to ni konec šifriranja

Pomembno je ločiti zgodbo od panike. Poročila poudarjajo, da to ni dokaz, da je P enak NP, saj je nova meja še vedno neprimerljivo počasnejša od česar koli polinomskega. Prav tako iz objavljenega dela ne izhaja noben praktičen napad na šifriranje. Eden od virov celo navaja, da metoda v praksi ne prehiti surove moči, razen pri neznansko velikih nalogah.

Kaj to pomeni zate? Neposredno skoraj nič: telefon, banka in gesla ostanejo varni. Posredno pa gre za opozorilo, da znajo umetnointeligenčni modeli prispevati k pravi matematiki in ne le pisati e-pošte. Če se rezultat potrdi, bodo morali raziskovalci predelati veliko člankov, ki so predpostavljali, da je hipoteza resnična. Če ne, bomo izvedeli, kako težko je preverjati dokaze, ki jih napiše stroj. V vsakem primeru je to ena najbolj zanimivih tehnoloških zgodb tega meseca, zato je pametno počakati na presojo strokovnjakov, preden verjameš naslovom.