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

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: . 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: . Vannak bizonyos elemi formuláink, amelyek pontosan a fenti alakban vannak tehát egy ilyen formula alakú, ahol az vagy vagy . 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 . igazság értékét.

Nyilván meg lehet csinálni nagyjából 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 -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ó.

<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16533029-6ae07d312f8d3' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16533029&origin=www.orulunkvincent.hu&obj_id=192691293-16533029-6ae07d312f8d3&n=1' data-name='like-post-frame-192691293-16533029-6ae07d312f8d3' 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>