Водещи AI лаборатории твърдят, че новите модели опровергават хипотезата за експоненциалното време (ETH)
Източник: TechCrunch / Complexity Theory Forum
Поредица от съвместни експерименти, проведени от водещи изследователски екипи в областта на изкуствения интелект, предизвика буря в академичните среди по теоретична информатика, след като авторите публикуваха резултати, демонстриращи устойчиво субекспоненциално решаване на класически трудни инстанции на задачата 3-SAT [1]. Ако изводите бъдат потвърдени, това би представлявало емпирично оспорване на хипотезата за експоненциалното време (ETH) – един от стълбовете на модерната теория на изчислителната сложност.
Механизъм на невронно-направляваното съкращаване на пространства от решения
Хипотезата за експоненциалното време постулира, че за най-лошите инстанции на NP-пълни проблеми времето за намиране на точно решение расте експоненциално с броя на променливите: $O(2^{\delta n})$. Традиционните алгоритми за търсене (като DPLL и CDCL солвъри) се сблъскват с експоненциална комбинаторна експлозия при преминаване през критичните фазови преходи (phase transitions).
Новото поколение reasoning модели обаче използва топологичен анализ на графа на зависимостите между булевите променливи. Чрез извличане на скрити геометрични симетрии в клаузите невронната мрежа успява да елиминира гигантски клонове от дървото на търсене още преди тяхното разгръщане, постигайки мащабиране, което при огромни масиви от променливи показва полиномиално или квазиполиномиално поведение.
Академичен скептицизъм: Най-лош случай срещу случайно разпределение
Теоретичните математици посрещнаха твърденията със сдържан скептицизъм. Основният аргумент на критиците е, че бенчмарковете, използвани от AI лабораториите, макар и генерирани при критичния коефициент на клаузи спрямо променливи ($m/n \approx 4.26$), все пак представляват случайни разпределения. Доказването на опровержение на ETH изисква решаване на конструирани инстанции за най-лошия възможен случай (worst-case), а не само средностатистически успехи върху милиони тестови примери.
Преосмисляне на границите на изчислимото
Независимо дали формалното математическо опровержение на ETH ще издържи стриктната проверка на академичната общност, практическите последици от тези резултати са революционни. За индустрията разликата между теоретичен най-лош случай и емпирично решим случай е фундаментална: ако 99.99% от реалните проблеми за оптимизация, разписание, логистика и протеинов дизайн могат да бъдат решени в полиномиално време от невронни системи, практическото значение на експоненциалната бариера изчезва.
Това развитие бележи сближаването на чистата математика с приложната мощ на мащабните изчислителни клъстери. Изкуственият интелект вече не е просто инструмент за статистическа интерполация, а се превръща в автономна изследователска сила, способна да открива невиждани алгоритмични преки пътища през вековни интелектуални лабиринти.
Четири стълба на дебата около алгоритмичната сложност и 3-SAT