AI-агент не решил задачу Conway, но сузил пространство поиска

AI-агент не доказал существование или невозможность Conway's 99-graph. Но он показал, как может выглядеть полезный результат от автономного исследователя: не громкое «решение», а проверяемые промежуточные границы, которые сужают пространство поиска.

Задача спрашивает, существует ли сильно регулярный граф с параметрами srg(99,14,1,2). В работе агент получил лучший подтверждённый артефакт на уровне 69,43% ограничений. Само число звучит внушительно только до тех пор, пока не вспомнишь: задача всё ещё открыта, а частичное выполнение ограничений не является доказательством существования графа.

Самая содержательная часть — структурная редукция. При λ=1 каждая окрестность вершины превращается в совершенное паросочетание, а при μ=2 внешние вершины можно сопоставить парам соседей, которые не соединены этим паросочетанием. В результате исходную задачу свели к поиску 12-регулярного графа на 84 вершинах. Эту конструкцию закодировали для CP-SAT и проверили на восстановлении уникального srg(9,4,1,2).

Есть и более узкий, но полезный отрицательный результат: среди циркулянтных графов на Z/99 не нашлось ни одного, удовлетворяющего более чем 68% ограничений — это 33 из 49 классов разностей. Такой же потолок получили для другой абелевой группы порядка 99. Отдельно проверили подход с заданными автоморфизмами на srg(9,4,1,2) и графе Пэли srg(13,6,2,3).

Ограничения здесь принципиальны. Четырнадцать разных методов не превысили отметку 69,43%, но это лишь устойчивая граница в рамках частичного зачёта, а не решение Conway's 99-graph. Более того, доказуемая граница ниже 4950 ограничений уже означала бы доказательство несуществования, поэтому задача связана с этими результатами гораздо теснее, чем может показаться по одному проценту.

Готовы ли вы считать такой воспроизводимый, но незавершённый результат успехом AI-исследователя — или для вас успех начинается только с полного доказательства? Источник: cs.AI updates on arXiv.org