Все новости

Соавтор гипотезы экспоненциального времени назвал её опровержение ИИ «ошеломляющей новостью»

Материал подготовлен Sintelligent с помощью ИИ. Опубликовано в SI: . Обновлено: .

ИИ помог опровергнуть гипотезу, на которой строились оценки сложности множества задач. Формальная проверка уже есть, но практическое ускорение начинается на задачах недостижимого размера, а вывод ещё разбирают специалисты.

Рассел Импальяццо, в 1998 году предложивший гипотезу экспоненциального времени (ETH) вместе с Рамамоханом Патури, назвал её опровержение «очень ошеломляющей новостью». ETH утверждала, что задачу выполнимости булевых формул 3-SAT нельзя решить за субэкспоненциальное время; от неё зависят условные оценки сложности в сотнях работ. По описанию OpenAI, опубликованные 26 октября работы OpenAI и Anthropic независимо предлагают алгоритмы со временем 2^o(n); созданные с существенным участием ИИ доказательства проверены в системе Lean. Импальяццо отметил, что исследователи скорее ожидали падения более строгих версий гипотезы. Практический эффект пока ограничен: по оценкам, приведённым The New York Times, проверенная граница OpenAI улучшает перебор лишь примерно от 10^2389 переменных, а вариант Anthropic для формул с пятью условиями на переменную — от 10^10000. Результат не отвечает на вопрос о равенстве P и NP и не ускоряет NP-задачи в целом. Импальяццо, Патури и Райан Уильямс участвуют в независимом разборе работы, но подчёркивают, что это не означает сертификации результата.

Источники 2

История

Модели OpenAI решают открытые задачи математики

11 событий
  1. Группа Дэвида Гросса опубликовала и подтвердила формальную проверку доказательства OpenAI по Янгу — Миллсу
  2. Соавтор гипотезы экспоненциального времени назвал её опровержение ИИ «ошеломляющей новостью»Открыто сейчас
  3. Anthropic: Claude нашёл алгоритм, опровергающий гипотезу экспоненциального времени для задачи 3-SAT
  4. OpenAI объявила три результата своих моделей: опровержение ETH, локальное сглаживание и Янга — Миллса
  5. OpenAI и Anthropic заявили, что их модели опровергли гипотезу экспоненциального времени
  6. Математики оспаривают, что OpenAI понимает собственное возможное доказательство задачи Навье — Стокса
  7. Эксперты спорят, может ли ИИ, решающий старые математические задачи, подорвать криптографию Bitcoin и Ethereum
  8. Математики усомнились, что OpenAI решила «ту самую» задачу Навье — Стокса: доказательство держится на искусственно подобранной внешней силе
  9. Модель OpenAI решила более сотни давних открытых задач математики — выпуск результатов будет согласовывать независимая группа из девяти математиков
  10. The Information: в OpenAI ждут, что скоро решат гипотезу Ходжа — вторую «задачу тысячелетия» за месяц
  11. ИИ-агенты OpenAI решили одну из «задач тысячелетия» — проблему Навье — Стокса за $1 млн