ETH теріске шығару: OpenAI мен Anthropic не дейді

ETH теріске шығару: OpenAI мен Anthropic не дейді

Екі бәсекелес ИИ-зертханасы өз модельдері экспоненциалдық уақыт гипотезасын (Exponential Time Hypothesis, ETH) теріске шығаратын алгоритмдер тапқанын мәлімдейді. Бұл гипотеза ондаған жылдар бойы көптеген есептеу тапсырмаларының қаншалықты қиын екенін дәлелдеудің іргетасы болды. Егер нәтижелер толық расталса, алгоритмдер теориясы кәдімгі күрделілік бағалауларының едәуір бөлігін қайта қарауға мәжбүр болады.

OpenAI мен Anthropic препринттер мен Lean формализацияларын 2026 жылдың қазан айының соңында жариялаған. Талқылаудың жаңа себебі Сан-Диего Калифорния университетінің 19 қарашадағы хабарламасы болды: гипотеза авторларын қоса алғанда, жетекші мамандар тұжырымдарды тәуелсіз тексеруді ұйымдастырады. Жариялау сәтінде бұл — белсенді ғылыми зерттеу нысаны, аяқталған жалпыға ортақ рецензия емес.

ETH деген не және ол неге маңызды

Бірнеше логикалық шарты бар тапсырманы елестетейік: әр шарт үш тұжырымның кемінде біреуі ақиқат болуын талап етеді. Барлық шарт бір мезгілде орындалатын айнымалы мәндерін табу керек. Бұл — 3-SAT тапсырмасы, NP-толық есептің классикалық мысалы.

Қарапайым шешу тәсілі - мәндердің барлық тіркесімін қарап шығу. n логикалық айнымалы үшін мұндай тіркесімдер саны 2^n. Айнымалылар саны өскен сайын n-нің аздаған өзгерісі де қарап шығу көлемін күрт ұлғайтады.

ETH гипотезасы 3-SAT үшін ең нашар жағдайда субэкспоненциалды алгоритм алу мүмкін емес деп тұжырымдайды: жұмыс уақыты n-ге экспоненциалды тәуелді, шартты түрде 2^(Ω(n)). Гипотезаны Рассел Импальяццо, Мохан Патури және Фрэнсис Зейн 1990-2000 жылдар шегінде тұжырымдаған.

ETH есептеу күрделілігі теориясында кең қолданылады. Зерттеушілер қорытынды тізбектерін құрады: егер ETH ақиқат болса, графтарға қатысты кейбір есептер, оңтайлы шешімдерді іздеу немесе деректерді өңдеу берілген шектен жылдам алгоритмге ие бола алмайды. Мұндай дәлелдерді шартты төменгі бағалар деп атайды.

ETH-тің болжамды теріске шығарылуы нені білдіреді

Редакциялық схема: ETH-тен шығатын экспоненциалды төменгі шек, мәлімделген субэкспоненциалды алгоритм және ғылыми тексеру кезеңдері. Бұл концептуалды салыстыру, нақты бағдарлама жылдамдығының графигі емес.

OpenAI не ұсынды

Жарияланған хабарламаға сәйкес, OpenAI зерттеу жүйесі 2026 жылдың 16 қазанында табиғи тілде дәлел алды, ал келесі күні компания нәтижені Lean-де формализациялады. Кейінірек жұмыс мәтіні мен формализация коды жарияланды.

Авторлар k-SAT есептері үшін бекітілген k кезінде субэкспоненциалды уақытта жұмыс істей алатын алгоритмді ұсынады. Формалды түрде бұл 2^(o(n)) түріндегі уақытты, қосымша полиномдық көбейткіштермен білдіреді. Мұндай нәтиже 3-SAT үшін осындай төмен асимптотикалық күрделіліктегі алгоритмге тыйым салатын ETH-ке қайшы келер еді.

Мұнда екі маңызды шектеу бар. Біріншіден, математикалық баға өте үлкен кіріс деректеріндегі уақыттың асимптотикалық өсуіне қатысты, бүгінгі нақты SAT-шешушінің кепілді жылдамдауына емес. Екіншіден, формалды дәлелді тексеру дәл жазылған математикалық теореманы растайды; формализацияның бүкіл мәлімделген интерпретацияға сәйкестігі де зерттелуі керек.

Anthropic не ұсынды

Көп ұзамай Anthropic ішкі Claude зерттеу моделіне телінетін өз жұмысын — «A 2^o(n) Time Algorithm for 3-SAT» — жариялады. Зерттеу сипаттамасында модель дербес жұмыс істеп, шешім іздеу үшін шамамен 14 млн шығыс токен жасағаны айтылады.

Anthropic сондай-ақ негізгі теоремасы мен тексеру құралдары бар Lean жобасын ұсынды. Репозиторийде нәтиже 3-SAT үшін детерминді субэкспоненциалды алгоритмнің бар болуы түрінде тұжырымдалған. Екі зертхананың материалдары қайта іске қосуға және тәуелсіз талдауға қолжетімді.

Олар бір іргелі мәселеге қатысты, бірақ техникалық құрылымдары мен дәлелдеу формасы бойынша ерекшеленеді. Екі тараптың жариялауы дәлелдерді сарапшылық талдауды әлі алмастырмайды.

Не тексерілді және не ашық күйінде қалады

Қауымдастықтың бір бөлігі формалды тексерулерді қайта шығара бастады. ETH: Community Examination and Discussion алаңында Lean жобаларын қайта іске қосу әрекеттері, теорема тұжырымдарына қатысты пікірлер және дәлелдердің күрделі бөліктерін түсіндіретін материалдар жарияланған. Кейбір қатысушылар ұсынылған формалды әзірлемелер өз тұжырымдарына қатысты тексеруден өтетінін растайды.

Бірақ тексерудің үш деңгейін ажырату керек: Lean коды қайта шығарыла ма; код мақаладағы дәл математикалық тұжырымды дәлелдей ме; классикалық ETH-ке қатысты бұл тұжырымның толық интерпретациясы дұрыс па. Әр деңгейде есептеу модельдері, кіріс деректерін кодтау және түрлендірулер уақыты туралы жеке сұрақтар туындауы мүмкін.

Тәуелсіз талқылауды ұйымдастыруды UC San Diego-дан Импальяццо мен Патури, сондай-ақ MIT-тен Райан Уильямс өз мойнына алды. Зерттеушілердің мәлімдемесінде ұйымдастырушылардың қатысуы нәтиженің дұрыстығын растау деп есептелмеуі керек екені ашық айтылған. Олар жұмыстарды ашық зерттеуді және ғылыми кездесулерді жоспарлап отыр.

Күрделілік теориясының маманы Лэнс Фортноу өз блогында нәтижеге қатысты оптимизм білдіріп, сонымен бірге дәлелді жеке тексермегенін атап өтті. Ол маңызды логикалық детальді де атап көрсетті: егер шартты гипотеза жалған болып шықса, бұрын одан шығатын қорытындылар міндетті түрде жалған бола қоймайды. Тек бұрынғы негіздемені сол қалпында қолдануға болмайды.

Бұл P мен NP мәселесін шеше ме

Жоқ. 2^(o(n)) уақытты дұрыс алгоритм кез келген полиномдық алгоритмнен әлдеқайда баяу болып қалуы мүмкін. Сондықтан ETH-тің теріске шығарылуынан P мен NP теңдігі шықпайды және барлық NP-толық есептерді шешудің әмбебап жылдам тәсілі пайда болмайды.

Интернетте қолданылатын криптожүйелер жақын арада бұзылады деген қорытынды жасауға да болмайды. Практикалық салдар нақты алгоритмдерге, олардың константаларына, есеп өлшемдеріне және басқа есептерді 3-SAT-қа түрлендіру мүмкіндіктеріне байланысты.

Нәтиженің теория үшін әлеуеті зор. Ол жаңа алгоритмдік бағаларға жол ашып, ETH-ті алғышарт ретінде пайдаланатын жүздеген зерттеуді қайта қарауға мәжбүр етуі мүмкін. Бірақ асимптотикалық теоремадан нақты бағдарламалық жасақтаманы жылдамдатуға дейінгі жол өте ұзақ болуы мүмкін.

Бұл оқиға ИИ үшін неге ерекше маңызды

Назарда брендтер жарысы емес, ғылыми жұмыстың жаңа тәртібі тұр. ИИ-жүйелер соншалықты күрделі дәлелдер ұсынады, оларды талдау үшін мамандардың ұжымдық күш-жігері, формалды тексеру жүйелері және тәуелсіз түсіндірмелер қажет.

Егер нәтиже тексеруден өтсе, бұл ИИ-дің іргелі математикадағы елеулі жетістігі болады. Егер олқылықтар табылса, жария талдау процедурасының өзі ғылыми қауымдастықтың модельдер көмегімен алынған барған сайын ауқымды нәтижелерді қалай тексеру керектігін көрсетеді. Ғылыми ашылу қайта шығаруға, түсінуге және тәуелсіз растауға келгенде ғана құнды болады.

Дереккөздер