OpenAI объявила о модели взлома индекса временной гипотезы

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

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