Внутренняя модель OpenAI подготовила заявленное опровержение гипотезы экспоненциального времени, предположения о сложности булевой выполнимости, на которое опираются сотни работ по информатике. Компания сообщила, что результат получен 16 октября, а на следующий день проверен машинным способом в языке Lean. Текст модели и доказательство в Lean опубликованы на GitHub. В случае подтверждения это важно, поскольку гипотезу использовали для оценки сложности задач теории графов, вычислительной биологии и баз данных.
Как OpenAI представила три результата
OpenAI объявила три результата в один день в областях информатики, математики и физики. В сообщении в блоге компания назвала гипотезу экспоненциального времени широко признанной и связала ее с проблемой P против NP. Заявление в информатике касается булевой выполнимости, центрального вопроса анализа сложности. Два других результата касаются гипотезы локального сглаживания, предложенной Кристофером Согге в 1991 году, и существования некоторых квантовых теорий поля в четырех измерениях. Все три результата приписаны внутренним моделям, а не внешним соавторам.
Проверка заявления в информатике строится на Lean и открытом доступе к материалам. OpenAI сообщила, что машинная проверка заявленного опровержения прошла 17 октября, через день после получения результата. Компания опубликовала на GitHub текст модели и доказательство в Lean для независимого изучения. В математике использован тот же подход с публикацией текста и доказательства в Lean, в продолжение 722 математических работ, выпущенных 6 октября. В физике подход иной: группа рецензентов решила пока не публиковать материалы, созданные ИИ, и подготовить собственное изложение.
Структура проверки ставит в центр авторов исходной гипотезы. Рассел Импальяццо и Рам Мохан Патури из UC San Diego и Райан Уильямс из MIT проверят заявление в теории сложности и подготовят объяснение. Импальяццо и Патури предложили гипотезу вместе с Фрэнсисом Зейном, поэтому экспертиза напрямую связана с ее происхождением. В открытом письме трое ученых отметили, что их участие не означает подтверждение результата. Уильямс сообщил, что группа не подписывала соглашений о неразглашении, не получит оплату, запросила все исходные данные и финансируемую конференцию, и OpenAI согласилась на оба условия.
Что подтверждение изменит для бизнеса
Для компаний, использующих оптимизацию, поиск и системы данных, практический эффект зависит от независимого подтверждения. Гипотеза поддерживала выводы о том, что многие задачи теории графов, баз данных и вычислительной биологии нельзя быстро решить. Проверенное опровержение потребует пересмотра этих аргументов о сложности и допущений при выборе решателей и оценке производительности. Небольшие команды, использующие готовые решатели, заметят это через обновленные рекомендации, а крупным организациям с собственными оптимизационными платформами понадобится глубокий пересмотр моделей, построенных на прежних нижних оценках.
Математическое и физическое заявления ставят отдельный рабочий вопрос о проверке и доверии. Доказательство локального сглаживания в любой размерности также закрыло бы гипотезу Какейя и гипотезу ограничения Стейна во всех размерностях после результата для двух измерений в 2019 году и гипотезы Какейя в трех измерениях в 2025 году. Физическая работа включает существование чистой теории Янга-Миллса, части задачи из списка Millennium Prize института Clay, наряду с квантовой хромодинамикой кварков и глюонов. Группа физиков под руководством нобелевского лауреата Дэвида Гросса, с участием Майкла Дугласа, Артура Джаффе, Игоря Клебанова и Никиты Некрасова, сама подготовит изложение, поэтому методы и ограничения пока нельзя оценить.
Признаком подтверждения станут итоги независимой экспертизы и обещанная конференция. Группа по информатике должна сообщить, выдерживает ли доказательство в Lean проверку и какие более слабые утверждения о сложности сохранятся при отказе от исходной гипотезы. Изложение по физике покажет, соответствуют ли доказательства существования стандартам сообщества без опоры на неопубликованные материалы модели. OpenAI заявила, что не претендует на академическое признание, отдает его ученым, подготовившим объяснения, и передала 5m долларов фонду Simons Foundation на семинары. Порядок признания и проверки покажет, могут ли результаты, полученные ИИ, перейти от объявления к применимым знаниям.
