OpenAI опровергла гипотезу, на которой держалась теория сложности вычислений

A.I. Just Blew Up a Key Tenet of Computer Science

OpenAI опровергла гипотезу, на которой держалась теория сложности вычислений

26 октября OpenAI объявила, что её новейшая ИИ-технология опровергла exponential time hypothesis — гипотезу, которую Russell Impagliazzo из University of California, San Diego предложил в 1998 году вместе с коллегами. Она утверждала, что некоторые задачи всегда останутся трудными для быстрого решения. Сама проблема P vs NP, одна из Millennium Prize problems, пока не решена, но результат открывает путь к принципиально новым вычислительным эффективностям.

Если P и NP следуют интуиции, то они определённо не должны быть равны.
  1. fsmv

    Старая новость, и доказательство ETH буквально не имеет никаких последствий для P vs NP или чего-либо ещё хоть отдалённо практичного

  2. peri-cl

    Кроме того

    https://news.ycombinator.com/item?id=50251661 («Гипотеза экспоненциального времени ложна [pdf] (github.com/openai)», 309 комментариев)

  3. matt3210

    Приманка для IPO

Ещё за этот день

2026-11-17