Може ли AI да създаде нова математика? За една секунда AlphaEvolve може да намери решение, което учените търсят от години

Google DeepMind представи AlphaEvolve – система, която използва големи езикови модели за откриване и проверка на нови комбинаторни структури. Тези структури могат да допринесат за развитието на изследванията в областта на теоретичната информатика, особено в сложността на приблизителното изчисление.

Изследователите отбелязват, че съвременните големи езикови модели вече са показали силни резултати в математиката и програмирането, но досега са имали слабо участие в откриването на нови теореми. Основният проблем тук е абсолютната коректност, която е от съществено значение в математиката. Всяко твърдение трябва да бъде или формално доказано, или проверено от експерт.

В статията „Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory“ (Усилено генериране на комбинаторни структури: Приложения към теорията на сложността) авторите описват как AlphaEvolve помага да се откриват нови конструкции, които след това автоматично се проверяват от компютър. Системата работи на принципа на еволюцията: тя генерира много програмни фрагменти, избира най-успешните и постепенно ги усъвършенства.

Този подход позволи постигането на напредък в две направления – в проблема MAX-4-CUT и в изследването на свойствата на случайните графи.

За задачата MAX-4-CUT досега беше известно, че не може да бъде апроксимирана по-добре от коефициент 0,9883. AlphaEvolve откри нова така наречена „джаджа“ – специална конструкция с 19 променливи и сложна система от тежести. Това подобри резултата до 0,987. В областта на теорията на апроксимацията подобни стъпки се смятат за значително постижение, тъй като всяка нова бариера е трудна за преодоляване.

Освен това системата изследва средната сложност на задачите върху случайни графи, където графите на Раманужан играят ключова роля. AlphaEvolve успя да намери такива графи за стотици върхове – значително повече, отколкото беше в състояние да направи преди това. Това помогна да се прецизират границите на изчислителната трудност и да се сближат почти напълно долната и горната оценка.

Основната особеност на работата е, че всички намерени конструкции бяха проверени за коректност не само чрез ускорени методи, но и чрез оригиналния „груб“ алгоритъм. Това гарантира надеждността на резултатите.

Авторите подчертават, че все още не става въпрос за това AI да може самостоятелно да доказва нови теореми, но още сега такива системи са в състояние да създават елементи на доказателства, които след това се „издигат“ в по-общи универсални резултати. В бъдеще ключовият проблем ще бъде проверката на верността, тъй като обемът на изчисленията за тази цел ще расте заедно със сложността на задачите.