Водещи лаборатории за ИИ твърдят, че моделите им опровергават хипотезата за експоненциалното време. Какво означава това?

Вчера OpenAI публикува решения на три значими математически проблема, които отдавна затрудняват изследователите. Едното беше изненадващо опровержение на хипотезата за експоненциалното време (ETH) — устойчиво допускане в компютърните науки, което играе голяма роля в разбирането ни за това какво е трудно за изчисляване.

Както и при предишните публикации на доказателства от водещата лаборатория, научните общности реагираха със смесица от възторг и тревога. Математикът от Anthropic Левент Алпьоге предположи, че OpenAI основава решенията си на вече съществуваща работа, а часове по-късно Anthropic публикува собствено опровержение на ETH.

Процесът на OpenAI обаче се развива. Този път лабораторията структурира публикациите си по различен начин за всяка от трите ангажирани дисциплини: математиците получиха работата, публикувана в GitHub; компютърните учени сформираха работна група, поискаха доказателствата да бъдат споделени публично, а OpenAI да финансира конференция за обсъждането им; физиците сформираха работна група, която ще определи как ще бъде публикуван резултатът им.

Професорът от MIT Райън Уилямс е компютърният учен, който организира реакцията на своята област към новото откритие. Уилямс, чиято работа е съсредоточена върху въпросите на изчислителната сложност, в миналото е критикувал подхода на OpenAI, като нарече публикуването на доказателствата от по-рано този октомври „DDOS атака срещу математиците“.

Той обаче се е съгласил да си сътрудничи с водещите лаборатории, за да помогне за развитието на идеи, жизненоважни за областта, каза той пред TechCrunch. Лабораторията го е помолила да помогне за интерпретирането на решението заедно с компютърните учени от UC San Diego Ръсел Импаляцо и Рамамохан Патури, които за първи път публикуват ETH през 1999 г.

Първата им стъпка беше да публикуват отворено писмо, призоваващо за обратна връзка от учени, интересуващи се от тези проблеми, както и за обсъждане на нормите около приноса на изкуствения интелект към тяхната работа.

„Някои части [от доказателството на OpenAI] са, може би бихте казали, рутинни, но след това да, има две или три части, които изглеждат извънземно, и точно тези части, които видях, ме накараха да си помисля: уау, това е нещо, върху което цялата общност трябва да работи заедно“, каза Уилямс пред TechCrunch.

Вие на страната на P срещу NP ли сте?

ETH е част от по-широк клас проблеми, известни като P срещу NP, които от десетилетия занимават компютърните науки и много други области. Казано опростено, изследователите се опитват да разберат дали всеки проблем, чието решение може лесно да бъде проверено (NP), може също така лесно да бъде решен (P).

Прост пример е играта судоку: щом решението на даден пъзел е налице, то може бързо да бъде проверено, но намирането на решението отнема време. Същата динамика се наблюдава при широк спектър от важни проблеми и това прозрение стои в основата на криптографските системи: когато разполагате с ключа към кодирано съобщение, можете да го разкриете, но действителното разбиване на ефективен код отнема твърде много време, за да бъде полезно.

Учените обаче все още не са доказали дали това винаги е така. „P = NP казва, че не само можете да проверите решенията на судоку, когато те съществуват, но и просто да ги генерирате“, каза Уилямс. „P = NP твърди, че това е вярно за всеки проблем, който можете да проверите бързо — ако можете да го проверите бързо, можете и да го решите бързо. Така че това просто изглежда твърде хубаво, за да е истина.“

Затова повечето учени приемат, че P ≠ NP. ETH предоставяше доказателства в тази посока. Тя по същество казва, че дори най-бързият компютърен алгоритъм се нуждае от експоненциално повече време, за да намери решение, с нарастването на броя на променливите в определен клас сложни логически пъзели.

Твърдението на OpenAI и Anthropic е, че техните модели са създали алгоритми, които решават тези пъзели за „субекспоненциално“ време, което означава по-бързо от смятаното дотогава за възможно. Ако това е вярно, те може да са доказали, че EFT е невярна — да са я опровергали, казано на научен език — и евентуално да са открили път към алгоритми, които по принцип постигат P = NP.

„Вероятно всеки компютърен учен трябва да отдава малко по-голяма тежест на правдоподобността на P = NP, но тежестта може да варира“, каза Уилямс. „Наистина смятам, че това поставя под въпрос голяма част от интуицията, която смятахме, че имаме относно … това доколко разрешими са [трудните NP проблеми]. Също така смятам, че това вероятно не е окончателният отговор. Не мисля, че алгоритъмът на OpenAI би могъл да бъде най-добрият възможен алгоритъм.“

Предстоящата работа за компютърните учени

Устойчивостта на ETH е довела до включването ѝ в много научни статии през последното десетилетие, които ще трябва да бъдат преразгледани, ако твърдението на лабораториите за изкуствен интелект, че са доказали нейната несъстоятелност, се потвърди, каза Уилямс.

„Това отчасти е причината да моля и да настоявам OpenAI да подкрепи конференция по темата — това ще засегне работата на много изследователи и трябва да разберем какво следва, освен да разберем алгоритмите; трябва да разберем какви трябва да бъдат основите, които имахме преди“, каза той.

Преди научните опасения идват въпросите за киберсигурността. Уилямс каза, че подобрен алгоритъм би могъл да означава, че криптографските системи, разчитащи на определени размери на ключовете, могат да бъдат смятани за разбити. Затова един от първите въпроси, които е задал на научния ръководител на OpenAI Дан Робъртс, „беше дали са проверили дали това засяга някакви криптографски системи … има ли сега нещо несигурно? И очевидно са проверили и са били сравнително уверени, че това … не означава, че има пробиви.“

Тази нова парадигма на научни открития чрез изкуствен интелект все още е в процес на развитие, но Уилямс казва, че е оптимист, въпреки реалните опасения, особено относно обучението на следващото поколение учени. Това, че е компютърен учен, който се занимава с математика на високо ниво, вероятно е улеснило адаптацията му в сравнение с тази на математиците, занимаващи се само с математика.

Все пак той казва, че изкуственият интелект „принуждава хората да бъдат малко по-амбициозни по отношение на вида работа, която вършат, и да мислят по-задълбочено: добре, ако всичко, върху което работех, вече е лесна плячка за изкуствения интелект, как мога да вдигна летвата за научните въпроси, които искам да задавам?“