Формулировка гипотезы занимает минуту, а победить её не удавалось с 1970-х: в графе без мостов (то есть без ребра, разрыв которого распадает граф надвое) должен найтись цикл-набор, проходящий по каждой связи ровно пару раз. Утверждение независимо предлагали Секереш и Сеймур. Частные случаи — планарные и кубические графы — закрыли, но общая формулировка застревала на снарках, против которых обычные приёмы не работают.
Как сообщает Хабр, OpenAI утверждает, что её модель нашла решение, подключив рой из 64 агентов: всё заняло менее часа. Само доказательство короткое — три страницы. И, что примечательнее, все приёмы в нём известны с середины 1980-х: новой теории в работе нет.
Выходит, рабочая связка лежала на поверхности не один десяток лет — мимо неё прошли и поколения математиков, и сами авторы гипотезы. Красивая сюжетная деталь для новости про ИИ. Правда, работает она только при одном условии: если доказательство устоит под проверкой специалистов. Пока об этом можно говорить лишь как о заявлении OpenAI.
Источник: Telegram: Хабр
Комментарии 2