👨💻 ИИ опроверг одну из главных гипотез информатики, заявляет OpenAI
Внутренняя модель компании нашла алгоритм, существование которого противоречит гипотезе экспоненциального времени (ETH). Гипотеза, выдвинутая в 1999 году, описывала, насколько быстро можно решать целый класс сложных комбинаторных задач.
📌 В таких задачах легко проверить решение, но гораздо сложнее найти его. Например, в судоку убедиться, что числа расставлены верно, можно за минуту, а вот решить его так быстро вряд ли получится, особенно если размер поля увеличивается с 9x9 до 1000x1000. К этому классу также относятся задачи на составление расписания, задача коммивояжера и тысячи других.
Если перебирать варианты один за другим, то с каждой новой переменной максимальное время, необходимое для решения, удваивается. Существуют альтернативные чуть более быстрые способы, однако ETH утверждала, что время всегда увеличивается экспоненциально. Тем не менее при работе алгоритма от OpenAI время растет медленнее экспоненты.
🎓 Доказательство записали на языке Lean и выложили на GitHub. Теперь проверить заявление компании могут все желающие. Научную группу проверяющих возглавят профессор MIT Райан Уильямс и двое авторов ETH — Рассел Импальяццо и Рамамохан Патури.
Осторожность объяснима. В начале октября OpenAI опубликовала 722 статьи о нерешенных математических задачах. Меньше чем через сутки три работы пришлось отозвать из-за ошибки. Некоторые математики раскритиковали такой подход. Филдсовский лауреат Теренс Тао назвал «токсичными отходами» доказательства, которые ИИ-компании массово выпускают в гонке за бенчмарками.
✏️ На ETH опираются сотни работ в теории графов, вычислительной биологии и базах данных. Если доказательство подтвердится, то выводы о том, что какие-то задачи нельзя решить быстрее, потеряют основания.
Но сами быстрые алгоритмы для этих задач из опровержения ETH не вытекают — и искать их придется отдельно.
Должен ли ИИ заниматься математикой?
❤️ — да, разумеется!
👎 — нет, математика только для людей
👋 Подпишитесь на Hi, AI!
Комментарии