Как сообщает BlockBeats, 27 октября OpenAI объявила, что ее модель искусственного интеллекта «решила» задачу ETH, что вызвало бурные обсуждения в технологическом и криптосообществах. Однако важно отметить, что в данном случае ETH – это не широко известная криптовалюта Ethereum, а важная гипотеза в компьютерной науке, существующая уже более двадцати лет: гипотеза об экспоненциальном времени (Exponential Time Hypothesis, сокращенно ETH).

Основной вопрос, который рассматривает гипотеза об экспоненциальном времени, заключается в следующем: насколько сложны задачи, которые кажутся «особенно трудными для решения»?

В качестве примера можно привести «задачу SAT» (задача о выполнимости булевых формул), о которой слышали многие. Она заключается в следующем: даны логические условия, можно ли найти такое присваивание значений, при котором все условия выполняются одновременно? Когда масштаб задачи увеличивается, лучший из известных на сегодняшний день методов заключается в последовательной проверке возможных ответов, при этом затраты времени растут в геометрической прогрессии с увеличением масштаба – то есть, как говорят, «в экспоненциальное время». ETH утверждает, что такие задачи по своей сути не могут быть значительно ускорены и не существует действительно эффективных алгоритмов «субэкспоненциального времени».

С момента своего выдвижения в 1999 году эта гипотеза является важным краеугольным камнем теоретической информатики. Сотни и тысячи научных статей основаны на ней для доказательства того, что «та или иная задача сложна» или «та или иной алгоритм близок к оптимальному». Если гипотеза ETH будет опровергнута, это будет означать, что для многих задач, которые мы считаем «практически невозможными для более быстрого решения», теоретически могут существовать лучшие решения.

В этот раз OpenAI заявила, что ее модель нашла детерминированный алгоритм, который может точно подсчитывать количество решений задачи k-SAT за субэкспоненциальное время, и провела формальную верификацию с использованием Lean. Если этот результат в конечном итоге выдержит экспертную оценку, он напрямую поколеблет гипотезу об экспоненциальном времени.