Суть проблемы и результат AI-атаки
Задача о графе Конвея (Conway's 99-graph problem) — это классическая проблема теории графов, спрашивающая, существует ли сильно регулярный граф с параметрами srg(99, 14, 1, 2). В новой работе, принятой к первой конференции CAISc (Conference For AI Scientists), автор Аалок Тхаккара демонстрирует систематическую, полностью воспроизводимую атаку на эту задачу с помощью автономного AI-агента.
Ключевой вывод исследователя: если будет доказано, что максимальная достижимая граница (bound) строго меньше 4950 (общего числа ограничений), то существование такого графа будет опровергнуто. AI-агент достиг верифицированного предела в 69.43% выполнения ограничений, что является текущим «фронтером» (границей).
Технические детали и редукция структуры
Исследование использует метод forced-structure reduction (принудительной редукции структуры). Благодаря параметрам λ=1 (соседние вершины имеют ровно 1 общего соседа) и μ=2 (несоседние вершины имеют ровно 2 общих соседа), задача сводится к поиску 12-регулярного графа на 84 вершинах. Эта структура закодирована для решения через CP-SAT (Constraint Programming-Satisfiability) и валидирована на восстановлении уникального графа srg(9,4,1,2).
Результаты по классам графов
AI-агент провёл исчерпывающий анализ циркулянтных графов на абелевых группах порядка 99. Результаты показывают, что ни один такой граф не может удовлетворить более 3366 из 4950 ограничений.
| Класс графов / Метод | Макс. доля ограничений | Количество ограничений | Примечание |
|---|---|---|---|
| Циркулянтные графы (Z/99) | 68.0% | 3366 / 4950 | Предел для всех абелевых групп порядка 99 |
| Лучший верифицированный артефакт | 69.43% | ~3437 / 4950 | Достигнут 14 различными методами |
| Порог непустоты (теоретический) | 100% | 4950 / 4950 | Любой результат < 4950 доказывает отсутствие графа |
Валидация через орбиты автоморфизмов
Авторы разработали фреймворк для проверки существования орбит автоморфизмов (с фиксированными точками и без). Этот подход был успешно протестирован на известных графах:
- srg(9,4,1,2) — уникальный граф, используемый для калибровки редукции.
- Paley graph srg(13,6,2,3) — классический сильно регулярный граф, подтвердивший корректность метода проверки орбит.
Почему это важно для AI-науки
Работа демонстрирует переход от «черного ящика» к верифицируемому AI-исследованию. Использование метрики частичного кредита (partial-credit metric) позволяет оценивать прогресс даже при отсутствии полного решения. Достижение 69.43% при 14 различных методах, ни один из которых не превзошел этот результат, указывает на то, что мы достигли устойчивого предела для текущих подходов к этой комбинаторной задаче. Любое дальнейшее продвижение потребует новых алгоритмических прорывов в области символьных вычислений и комбинаторики.
Источник: arXiv cs.AI ↗