[Перевод] Две лаборатории против одной гипотезы: что происходит вокруг ETH
OpenAI и Anthropic сообщили, что их исследовательские модели нашли алгоритмы, опровергающие гипотезу экспоненциального времени — ETH. На этом предположении построены многочисленные оценки сложности вычислительных задач. Если результат выдержит проверку, исследователям придётся пересмотреть часть представлений о том, какие алгоритмы вообще возможны. Масштаб последствий зависит от того, какое ускорение обещают новые алгоритмы. Для этого нужно разобраться в связи ETH с проблемой P против NP. Читать далее