exponenciálisidő-hipotézis
Angol megfelelő: Exponential Time Hypothesis, röviden ETH
Az exponenciálisidő-hipotézis a számítástudomány egyik alapfeltevése, Russell Impagliazzo és Ramamohan Paturi fogalmazta meg: azt állítja, hogy a 3-SAT nevű logikai feladványra nincs olyan módszer, amelynél a munka a feladvány méretével ne nőne exponenciálisan. 2026 októberében az OpenAI és az Anthropic is közzétett egy-egy cikket, amely szerint a saját belső modelljük által talált algoritmus megcáfolja; ez a szócikk írásakor bejelentett, lektorált megjelenés nélküli eredmény.
Mit állít? A 3-SAT feladványban kapcsolók vannak, mindegyik be- vagy kikapcsolt állásban, mellettük feltételek, amelyek mindegyike legfeljebb három kapcsoló állásáról szól (például: „az első be van kapcsolva, vagy a második ki van kapcsolva”). A kérdés az, van-e olyan beállítás, amelyben minden feltétel teljesül. Egy kész beállítást könnyű ellenőrizni, megtalálni viszont nehéz: a nyers módszer minden lehetséges állást végigpróbál, így minden új kapcsoló megduplázza a munkát. Az Anthropic cikke szerint a végigpróbálás már 100 kapcsolónál kivárhatatlan. A kutatók évtizedek alatt faragtak a szorzón, a cikk szerint a korábbi legjobb determinisztikus módszer kapcsolónként nagyjából 1,328-szorosra vitte le a duplázást. Az exponenciálisidő-hipotézis azt mondja, hogy a szorzón lehet faragni, de egy határ alá nem: van egy egynél nagyobb szám, amelynél kisebb szorzóval egyetlen módszer sem dolgozik.
Miért alapfeltevés? Bizonyítani senki nem tudta, mégis sok eredmény épül rá. Ha egy feladatról meg kell mutatni, hogy reménytelenül nehéz, a kutatók gyakran azt bizonyítják, hogy a gyors megoldása a 3-SAT gyors megoldását is jelentené. Az Anthropic cikkének saját irodalomkutatása több mint 800 tanulmányt talált, amely legalább egy saját eredményét csak erre a hipotézisre vagy egy erősebb rokonára építve bizonyítja. A cikk szerint a hipotézis erősebb állítás, mint a széles körben elfogadott P ≠ NP sejtés: nemcsak azt mondja, hogy a 3-SAT-ra nincs gyors módszer, hanem azt is, hogy a lassú módszer legalább mennyire lassú.
Mit jelent a cáfolat? Az Anthropic cikke szerint egy belső Claude-kutatómodell 2026. október 16-án, emberi beavatkozás nélkül talált olyan algoritmust, amelynél a munka a kapcsolók számával már nem nő exponenciálisan, sőt a teljesítő beállítások számát is megadja. Az OpenAI előzetes közleménye ugyanerre jut, más matematikai úton. Mindkét cikk szerint ezzel a hipotézis szigorúbb változata, az erős exponenciálisidő-hipotézis (SETH) is megdől. A cáfolat státusza: bejelentett, nem elfogadott. Mindkét cikk a labor saját, előzetes közleménye, lektorált folyóiratban a szócikk írásakor nem jelent meg. Az Anthropic bizonyítását a Lean 4 nevű bizonyításellenőrző program is lefuttatta, a labor saját megjegyzése szerint viszont azt, hogy a gépi változat pontosan a cikk állítását mondja-e ki, gép nem ellenőrzi, azt az olvasónak kell összevetnie.
Mit NEM jelent? Mindkét cikk kimondja a saját határait. Az Anthropic szerint az eredmény a P kontra NP kérdést közvetlenül nem dönti el, gyakorlati algoritmust sem ad: tisztán aszimptotikus, vagyis csak csillagászati méretnél érvényes. A cikk számítása szerint egy tipikus feladványtípusnál az új módszer csak akkor gyorsabb a nyers végigpróbálásnál, ha a kapcsolók száma meghaladja azt a számot, amelyet egy egyes és utána tízezer nulla ír le. Az OpenAI cikke szerint az eredményből nem következik, hogy az általános NP-feladatokra is volna ilyen algoritmus. A titkosításra gyakorolt hatásról egyik cikk sem nyilatkozik, ezért erről a szócikk sem állít semmit.
Példa: Egy hétfős pécsi fuvarozó cég vezetője a hírekben azt olvassa, hogy az AI megdöntötte a számítástudomány egyik alapfeltevését. Két kérdése van: gyorsabb lesz-e ettől a túratervező programja, illetve kell-e most bármit lépnie. Az első kérdésre maguk a cikkek felelnek: az új algoritmus a gyakorlatban nem gyorsít semmit, csak olyan méretnél előnyös, amilyen feladvány a valóságban nem fordul elő, tehát a túratervezőt sem teszi elavulttá. A második kérdésre a válasz: nem. A hír ettől még valódi, csak máshol van a jelentősége. Egy AI-modell önállóan talált olyan eredményt, amelynek az ellenkezőjére a szakma több száz tanulmányt épített, a laborok pedig nem azt kérték, hogy higgyenek nekik: közzétették a cikket, a gépi ellenőrzést, valamint a saját korlátaikat. A józan tanulság egy cégvezetőnek ebből jön. Az AI-tól kapott eredmény akkor ér valamit, ha ellenőrizni lehet, a szállító pedig maga mondja meg, mire nem jó. Aki AI-eszközt vezet be, ugyanezt kérheti: ne a magabiztos válasz döntsön, hanem az, amit egy második forrás vagy egy ember vissza tud mérni.
Forrás: R. Impagliazzo, R. Paturi: On the complexity of k-SAT. Journal of Computer and System Sciences 62(2):367–375, 2001, doi:10.1006/jcss.2000.1727 (a hipotézis megfogalmazása; a hivatkozási adatok az Anthropic-cikk irodalomjegyzékéből). Ennek konferenciaváltozata: R. Impagliazzo, R. Paturi: Complexity of k-SAT, Paturi egyetemi honlapján: https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_1999_ccc.pdf (a definíció „ETH (Exponential-Time Hypothesis)” néven). Claude (Anthropic): A 2^o(n) Time Algorithm for 3-SAT, 2026. október 26., cikk és Lean 4 formalizálás: https://github.com/anthropics/formal-math/tree/main/eth (a 3-SAT leírása, a 100 kapcsolós és az 1,328-as adat, a több mint 800 tanulmány, a P ≠ NP-vel való viszony, az október 16-i dátum, a gyakorlati határ, a Lean-ellenőrzés korlátja). OpenAI: The Exponential Time Hypothesis is False, előzetes közlemény, kelte 2026. október 17., átdolgozva október 25.: https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf (a cáfolat és az NP-feladatokra vonatkozó korlát). Mindhárom 2026-11-07-én letöltve. A kapcsolós hasonlat, a fuvarozó-példa, valamint a túratervezésre vont következtetés a szótár saját értelmezése.
Rokon fogalmak: Anthropic, OpenAI, Claude, AI-labor, frontier, hallucináció