OpenAI bejelentette, hogy megcáfolták az Exponential Time Hypothesis-t.

2026.10.27 by jotunder

Az ETH megcáfolásának bejelentését sokkal óvatosabban intézte az OpenAI, mint a hétszázhuszonkét kézirat nyilvánosságra hozatalát. Megegyezett a téma három gurujával, hogy ők ezt most átnézik és utána konferenciát rendeznek az eredményekről, az OpenAI pedig minden részletet nyilvánosságra hoz.

Gyakorlatilag érthető, hogy miről van szó, ezért leírom ebben a posztban.

Íme egy alapformula: $A\vee B\vee \neg C$ . Ez a formula pontosan akkor igaz, ha A, B illetve a C tagadása közül legalább egy teljesül. Tehát ha A az, hogy Franciaország fővárosa Berlin, B az, hogy Németország fővárosa Párizs és C az, hogy Svájc fővárosa Zürich, akkor a formula igaz, ha Zürich helyett Bern-t írunk, akkor már nem.

Képzeljük el, hogy n darab változónk van: $X_1, X_2, \dots X_n$ . Vannak bizonyos elemi formuláink, amelyek pontosan a fenti alakban vannak tehát egy ilyen formula $Y_i \vee Y_j \vee Y_k$ alakú, ahol $Y_i$ az vagy $X_i$ vagy $\neg X_i$ . A feladat az, hogy írjunk egy programot, ami eldönti, hogy lehet-e igaz mindegyik ilyen választott elemi formula egyszerre, ha ügyesen választjuk meg a $X_1, X_2, \dots X_n$ . igazság értékét.

Nyilván meg lehet csinálni nagyjából $2^n$ lépésben, ha kipróbáljuk az összes lehetséges behelyettesítést. A kérdés az, hogy megcsinálhatjuk-e szignifikánsan gyorsabban, tehát szubexponenciális időben. Az Exponential Time Hypothesis szerint nem lehet megoldani. Ez azt jelenti, hogy ez a probléma, amit 3-SAT-nak neveznek csak exponenciális időben oldható meg, és akkor minden ún. NP-teljes döntési problémára igaz és a klasszikus döntési problémák általában ilyenek. Ha bebizonyítják az ETH-t azt jelentette volna, hogy P nem egyenlő NP-vel, nem lehet minden értelmes döntési feladatot polinomiális időben megoldani (ezt nem sokan gondolják amúgy).

Az ETH cáfolata persze nem jelenti P-t sem, tehát nem dönti el a $P \neq NP$ -t ami az algoritmuselmélet legnagyobb problémája (és az egyik Millenium probléma). Ennek ellenére az algoritmuselmélet történetének vélhetően legnagyobb eredménye az, amit most az OpenAI nyilvánosságra hozott. Az OpenAI algoritmusa ugyan szubexponenciális, de azért módjával, nem fenyeget a veszély, hogy most hirtelen mindenféle kódokat fognak feltörni. Ez a hír nem lesz benn a sajtóban, pedig….

P.S latex pluginnal lehetne szebben, de legyen ez most jó.

P.P.S ebből nem következik, hogy minden döntési probléma megoldható szubexponenciális időben.

<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16533029-6ae3692644332' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16533029&origin=www.orulunkvincent.hu&obj_id=192691293-16533029-6ae3692644332&n=1' data-name='like-post-frame-192691293-16533029-6ae3692644332' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>

51 Commments

@AI szagerto: engem az érdekelne nagyon, hogy ki tudna a saját területén (és néhány agyoncikkezett területen, pl. orvosi diagnosztika stb.) kívülről megnevezni pár field-changing problémát anélkül, hogy a kérdést előbb megkonzultálná egy modellel? Mi újság a balti-szláv filológiában, vagy éppen a korai mongol birodalom kronológiájában? Remélem érthető, mit akarok mondani, mennyit látunk át abból valójában, ami történik? Biztos, hogy X szakma/tudomány – bármely kiváló – művelője felfog bármit is abból, hogy Y szakma/tudomány éppen hogy áll az AI vagy bármi más kapcsán?
Időnként olvasok itt hihetetlen zöldségeket olyan témában, amiben véletlen benne van a 10 000 órám, és elgondolkodom, hogy mi lehez az oka az önkritika teljes elvetésének, amikor valaki általa abszolút át nem látott dolgokban nyilvánul meg alkalmanként kifejezetten lekezelő stílusban.

Hiv.: [@jack_of_all_trades:](#comment-356331)

jack_of_all_trades szerint:

2026.10.29 15:52

@AI szagerto: engem az érdekelne nagyon, hogy ki tudna a saját területén (és néhány agyoncikkezett területen, pl. orvosi diagnosztika stb.) kívülről megnevezni pár field-changing problémát anélkül, hogy a kérdést előbb megkonzultálná egy modellel? Mi újság a balti-szláv filológiában, vagy éppen a korai mongol birodalom kronológiájában? Remélem érthető, mit akarok mondani, mennyit látunk át abból valójában, ami történik? Biztos, hogy X szakma/tudomány – bármely kiváló – művelője felfog bármit is abból, hogy Y szakma/tudomány éppen hogy áll az AI vagy bármi más kapcsán?
Időnként olvasok itt hihetetlen zöldségeket olyan témában, amiben véletlen benne van a 10 000 órám, és elgondolkodom, hogy mi lehez az oka az önkritika teljes elvetésének, amikor valaki általa abszolút át nem látott dolgokban nyilvánul meg alkalmanként kifejezetten lekezelő stílusban.

Hiv.: [@jack_of_all_trades:](#comment-356331)

Loading...