OpenAI и Anthropic заявили, что их ИИ опроверг гипотезу ETH
OpenAI и Anthropic заявили, что их ИИ опроверг гипотезу ETH Две лаборатории независимо опубликовали алгоритмы, которые решают задачу 3-SAT быстрее, чем допускает гипотеза экспоненциального времени (ETH). На ней 27 лет держатся оценки сложности в сотнях работ. У Anthropic результат 16 октября нашла внутренняя версия Claude, доказательство проверено в Lean 4. Препринт OpenAI описывает детерминированный подсчёт решений k-SAT за субэкспоненциальное время. Работы проверяют Рассел Импальяццо, один из авторов гипотезы, а также Рамамохан Патури и Райан Уильямс. Импальяццо пока «не уверен на 100%». На задачах меньше примерно 10 млн переменных практического ускорения не будет. Источники: https://www.science.org/content/article/ai-cracks-27-year-old-pillar-computer-science-openai-and-anthropic-claim https://hexagonmath.org/2610.00577v1 #AI #OpenAI #Anthropic #Математика #Наука