OpenAI утверждает, что с помощью нового алгоритма опровергла гипотезу экспоненциального времени

ChainCatcher сообщает, что недавно OpenAI объявила, что её ИИ-модель разрешила гипотезу экспоненциального времени, широко используемую в компьютерных науках более 20 лет, с английской аббревиатурой ETH — не Ethereum. Эта гипотеза исследует, насколько сложны особо трудные для вычисления задачи, и приводит в качестве примера проблему булевой выполнимости (SAT): при заданном наборе логических условий существует ли такое присваивание значений, при котором все условия выполняются одновременно. По мере увеличения масштаба задачи известные лучшие методы сводятся к перебору возможных решений, при этом временные затраты растут экспоненциально с ростом масштаба. Гипотеза экспоненциального времени далее утверждает, что такие задачи принципиально невозможно значительно ускорить — не существует по-настоящему эффективных субэкспоненциальных алгоритмов. С момента её формулировки в 1999 году эта гипотеза стала важнейшим фундаментом теоретической информатики: множество статей используют её для доказательства сложности некоторых задач и того, что некоторые алгоритмы уже близки к оптимальным. Если гипотеза экспоненциального времени будет опровергнута, это означает, что многие задачи, считавшиеся практически невозможными для ускорения, теоретически могут иметь более эффективные решения. OpenAI утверждает, что её модель нашла детерминированный алгоритм, позволяющий точно подсчитать количество решений задачи k-SAT за субэкспоненциальное время, и провела формальную верификацию с использованием Lean. Если этот результат выдержит проверку экспертами, он напрямую подорвёт гипотезу экспоненциального времени.