Модели OpenAI и Anthropic опровергли гипотезу экспоненциального…

Модели OpenAI и Anthropic опровергли гипотезу экспоненциального времени (ETH), согласно которой задача 3-SAT для булевых формул не может быть решена быстрее экспоненциального времени от числа переменных. Обе компании опубликовали формализованные на языке Lean доказательства опровержения. Доказательство OpenAI дополнительно позволяет предсказывать число решений булевых формул за субэкспоненциальное время. Результаты пока не прошли независимую проверку: сотрудники OpenAI передали материалы группе специалистов по теории сложности, в которую вошли авторы исходной формулировки гипотезы.

🔬 Факты