OpenAI и Anthropic утверждают, что решили задачу 3-SAT за время 2^o(n), опровергая гипотезу об экспоненциальном времени

Компании OpenAI и Anthropic заявили о решении NP-полной задачи 3-SAT за время, превосходящее экспоненциальную сложность, что потенциально опровергает Экспоненциальную гипотезу времени (ETH). Утверждение вызвало широкое обсуждение в научном сообществе, так как имеет фундаментальные последствия для теории вычислительной сложности и ограничений ИИ.