OpenAI заявила о прорыве в теории сложности, эксперты сомневаются в угрозе для Bitcoin

26 октября OpenAI объявила: её ИИ-система опровергла гипотезу экспоненциального времени (ETH) — предположение о том, что некоторые логические задачи в худшем случае решаются только за экспоненциально большое время. Речь о задаче 3-SAT, где компьютер ищет набор значений «истина/ложь», который удовлетворяет набору логических условий.

Компания утверждает, что результат проверен в системе формальных доказательств Lean. Но её пояснительная записка описывает более слабую субэкспоненциальную оценку времени, чем самое сильное утверждение в рукописи. Статья датирована 17 октября и обновлена 25 октября. В ней заявлен детерминированный алгоритм, который точно подсчитывает выполнимые наборы булевых формул фиксированной ширины за субэкспоненциальное время и полиномиальную память. Задача от этого не становится простой для современных компьютеров, и P=NP это не доказывает.

Математики Райан Уильямс, Расселл Импальяццо и Мохан Патури, которых попросили организовать независимую проверку, подчеркнули в письме: «Наше участие не следует считать подтверждением заявления». Уильямс также рассказал, что попросил OpenAI проверить, не скомпрометированы ли существующие криптосистемы. Ответ компании: они «видимо, в безопасности» — но, по его собственным словам, это не independent криптографический аудит.

Авторы материала CryptoSlate отмечают: заявленный результат касается решения SAT-формул, а не напрямую майнинга или подписи транзакций Bitcoin. Майнинг — это поиск хеша блока ниже целевого значения, подпись — авторизация трат через ECDSA и Schnorr на кривой secp256k1 (BIP340), которые основаны на сложности дискретного логарифмирования. Теоретическая оценка для SAT не доказывает ни практического преимущества в майнинге, ни способа восстановить приватный ключ. OpenAI сама признаёт: для практических улучшений нужны дальнейшие исследования.