OpenAI и Anthropic опровергли гипотезу ETH, обнулив часть теоретической информатики

OpenAI и Anthropic заявили, что опровергли гипотезу экспоненциального времени (ETH), на которой 27 лет строились работы по теории сложности. Доказательства опубликованы на GitHub в Lean-формате, но независимо не проверены; OpenAI просит исследователей UCSB и MIT помочь с разбором.

• ETH утверждала: время решения задач растёт экспоненциально с их размером
• Доказательства выложены на GitHub в тексте и машиночитаемом Lean
• Профессор UCSB Локштанов ждёт, что ~50 его статей станут «бессмысленными»
• OpenAI обещала финансировать конференцию по разбору результата