OpenAI опровергла гипотезу, на которой держалась теория сложности вычислений
A.I. Just Blew Up a Key Tenet of Computer Science

26 октября OpenAI объявила, что её новейшая ИИ-технология опровергла exponential time hypothesis — гипотезу, которую Russell Impagliazzo из University of California, San Diego предложил в 1998 году вместе с коллегами. Она утверждала, что некоторые задачи всегда останутся трудными для быстрого решения. Сама проблема P vs NP, одна из Millennium Prize problems, пока не решена, но результат открывает путь к принципиально новым вычислительным эффективностям.
Если P и NP следуют интуиции, то они определённо не должны быть равны.
- fsmv
Старая новость, и доказательство ETH буквально не имеет никаких последствий для P vs NP или чего-либо ещё хоть отдалённо практичного
- peri-cl
Кроме того
https://news.ycombinator.com/item?id=50251661 («Гипотеза экспоненциального времени ложна [pdf] (github.com/openai)», 309 комментариев)
- matt3210
Приманка для IPO