Ritkán fordul elő, hogy egy matematikai-számítástudományi állítás egyszerre legyen nagyon elvont és mégis ennyire gyakorlati jelentőségű. Most pont ez történt: egy régóta használt feltevés dőlhet meg, amihez kutatók egész sorának kell újraszámolnia, mit gondol a „nehéz” problémákról.

Mi történt

OpenAI három nagy matematikai jellegű eredményt tett közzé, ezek közül az egyik az Exponential Time Hypothesis, röviden ETH cáfolatáról szól. Az ETH a számítástudomány egyik tartós munkafeltételezése: leegyszerűsítve azt mondja ki, hogy bizonyos különösen nehéz logikai problémák megoldásához a legjobb algoritmusoknak is nagyon gyorsan növekvő, úgynevezett exponenciális időre van szükségük, ahogy nő a feladat mérete.

Ez elsőre száraznak hangzik, de a tét nagy. A kérdés a P versus NP problémakörhöz kapcsolódik, amely arról szól, hogy ami gyorsan ellenőrizhető, az vajon gyorsan meg is oldható-e. Gondolj a Sudokuhoz hasonló feladatokra: egy kész megoldást gyorsan le tudsz ellenőrizni, de magát a jó megoldást megtalálni már sokkal nehezebb. Az ETH ehhez a világhoz adott egy fontos kapaszkodót, mert azt sugallta, hogy bizonyos problémák tényleg makacsul nehezek maradnak.

Az új állítás lényege, hogy a modellek olyan algoritmust találtak, amely ezeket a problémákat nem exponenciális, hanem úgynevezett szubexponenciális időben oldja meg. Ez azt jelenti, hogy a futási idő továbbra is nő a bemenet méretével, de nem olyan brutálisan, mint korábban hitték. Ha ez helyes, akkor az ETH nem tartható ebben a formában. Nem sokkal később Anthropic is közzétett egy saját ETH-cáfolatot, miközben a szakmai közösség azonnal szervezkedni kezdett a bizonyítások ellenőrzésére.

Miért fontos

Az ügy nem azért érdekes, mert holnaptól gyorsabb lesz a laptopod, hanem mert az elméleti számítástudomány alaprétege mozdulhat el. Az ETH-re az elmúlt években rengeteg tanulmány épített: ha egy feladatot erről a feltevésről kiindulva „biztosan nehéznek” tekintettek, azt most újra kell vizsgálni. Ez még nem jelenti azt, hogy hirtelen P = NP lett, vagy hogy a mai titkosítások összeomlanak. Inkább arról van szó, hogy a korábbi intuíciók gyengülhetnek. Ryan Williams, aki a terület válaszának szervezésében is részt vesz, úgy látja, ez növeli annak esélyét, hogy a kutatók komolyabban vegyék a P = NP lehetőségét, még ha ez messze nem is végső bizonyíték.

Közben az is látszik, hogy nemcsak maga az eredmény, hanem a tudományos közzététel módja is változik. Ahelyett, hogy egy hagyományos, lassú lektorálási folyamatban jelenne meg minden, a közösségek munkacsoportokat szerveznek, nyílt visszajelzést kérnek, és konferenciát sürgetnek. Ez olyan, mintha egy kész cikk helyett egy fél laborasztalt borítanának a szakmára: azonnal sokan dolgozhatnak rajta, de a feldolgozás is nehezebb.

Mire figyelj

  1. A legfontosabb kérdés az ellenőrzés. Az ilyen bizonyítások értéke azon múlik, hogy független kutatók lépésről lépésre megerősítik-e őket.
  1. Érdemes figyelni, pontosan mennyire erős az új algoritmus. Egy ETH-cáfolat önmagában még nem egyenlő azzal, hogy a teljes P versus NP kérdés megoldódott.
  1. Külön téma lesz a kriptográfia. Ez a modern titkosítás matematikai alapja; ha egy új algoritmus bizonyos problémákat túl gyorsan old meg, egyes rendszerek gyengülhetnek. Egyelőre nem az látszik, hogy azonnali gyakorlati törés következne.
  1. Hosszabb távon az is fontos, hogyan alakítja át ez a kutatói munkát. Ha az AI egyre több „alacsonyan lógó gyümölcsöt” leszed az elméleti kutatásban, a tudósoknak magasabbra kell tenniük a kérdéseiket — és ez talán a mostani hír legmaradandóbb következménye lehet.