OpenAI объявила о «субэкспоненциальном» алгоритме для SAT, но он работает только после 10^10^10^10^10^10 переменных
Efficient algorithms, the Exponential Time Hypothesis, and losing the plot
В 1965 году Джек Эдмондс ввёл понятие «хорошего» алгоритма, которое позже превратилось в полиномиальное время. С тех пор это определение оказалось несовершенным: оно породило «галактические» алгоритмы, нереализуемые во Вселенной. На этой неделе OpenAI заявила о прорыве — субэкспоненциальном алгоритме для задачи выполнимости (SAT). Однако, как выяснил автор, до числа переменных порядка 10^10^10^10^10^10 алгоритм использует полный перебор, то есть экспоненциальное время. Для любых мыслимых задач это не меняет ничего.
Заявленный субэкспоненциальный алгоритм для задачи выполнимости — прямое доказательство того, что наше определение эффективности было даже хуже, чем мы думали 50 лет назад.