Ленс Фортноу пишет о вычислительной сложности больше двадцати лет и не склонен к громким восклицаниям. Свой пост о новом заявлении он закончил осторожной фразой: «Я сам не проверял доказательство, но теперь можно смело считать, что гипотеза экспоненциального времени мертва» (Computational Complexity).
Заявление пришло от двух лабораторий. OpenAI, компания, стоящая за ChatGPT, говорит, что её модель опровергла гипотезу экспоненциального времени, обычно её сокращают до ETH. Через несколько часов Anthropic, создатель Claude (оба ассистента мы сравнивали здесь), опубликовала собственное опровержение. После этого в заголовках новость связали со спором математиков и со страхами за мировое шифрование. Мы прочитали материалы обеих лабораторий, комментарии экспертов и новостное освещение, и наш вывод прост: результат, скорее всего, настоящий и важный для теоретиков, но менять то, как вы защищаете свои данные, из-за него не нужно. Две из трёх громких тем касаются других споров, а третья — тренда.
Что такое гипотеза экспоненциального времени простыми словами?
Начнём с головоломки под названием 3-SAT. Есть длинный список условий над n переключателями «вкл/выкл», каждое условие выглядит как «A, или не B, или C», и нужно подобрать положение переключателей, при котором выполнены все условия сразу. Проверить предложенный вариант быстро. Найти его — вот это сложно, как в судоку: готовую сетку проверить легко, а пустую заполнить нет.
ETH, предложенная в 1999 году Расселлом Импальяццо и Рамамохаяном Патури (вместе с Фрэнсисом Зейном), утверждает, что любому алгоритму для 3-SAT требуется время, растущее как 2 в степени c·n при некотором фиксированном c больше нуля (Fortnow). Представьте кодовый замок, где каждый дополнительный диск умножает объём работы на фиксированный множитель, скажем 1,3. ETH говорит, что этот множитель можно уменьшать, но до 1 он не опустится никогда.
Опровержение утверждает, что по мере роста формул множитель всё-таки стремится к 1. По словам Фортноу, статья OpenAI даёт время работы порядка 2 в степени n·log log n / √(log n). Это всё равно далеко не быстро: оно просто растёт медленнее, чем при любом фиксированном множителе. Anthropic в своём описании прямо оговаривает: «Результат чисто асимптотический и ничего не говорит о решении формул на практике» (Anthropic).
Почему теоретики так всполошились? ETH использовали в сотнях статей как замену утверждению «эту задачу нельзя решить намного быстрее» (OpenAI). Если гипотеза ложна, эти аргументы о сложности придётся перепроверять, хотя Фортноу отмечает: «то, что ETH и SETH неверны, не значит, что их следствия ложны».
Проверено больше обычного, но до «решено» далеко
Проверки уже больше, чем получает большинство прорывов за первую неделю. OpenAI говорит, что её модель нашла опровержение за десять дней до анонса и что оно формализовано в Lean — системе проверки доказательств, которая принимает только шаги, поддающиеся верификации (OpenAI). Anthropic сообщает, что свою версию нашла внутренняя модель Claude, а файлы Lean написали ИИ-модели (Anthropic).
Затем подключились люди. Райан О'Доннелл из Carnegie Mellon выложил переписанное изложение доказательства, а по словам Фортноу, Шива Кинтали выложил ещё одно; оба стремятся к простоте, а не к лучшим оценкам. Тимоти Гауэрс назвал это «Очень неожиданным и значимым: то, что она неверна» (Business Insider).
Формально проверять результат поручено Импальяццо, Патури и Райану Уильямсу из MIT. Он сказал TechCrunch, что часть доказательства рутинна, но «есть две-три чужеродные на вид части». Business Insider пишет, что Уильямс результат не заверял, а группа подчёркивает: её участие не означает одобрения. И ещё одна оговорка из репозитория Anthropic: Lean проверяет доказательства, но «никакая машина не проверяет, что этот файл говорит то же, что статья», так что короткий файл с формулировками должен прочитать человек. Именно поэтому его и сделали коротким.
Наш вывод: заявление двух лабораторий, машинно проверенные доказательства и переписанные людьми версии за считаные дни — это необычно сильный набор. Но пока эксперты и журнал не скажут иного, это всё ещё заявление.
Спор математиков — об этом результате?
Преимущественно нет. «Ссора математиков» из заголовка BBC касается другой задачи. В материале речь о споре вокруг уравнений Навье — Стокса: Тристан Бакмастер из NYU спросил, не могли ли его черновики, хранившиеся в инструменте OpenAI Codex, попасть в собственную работу OpenAI. В OpenAI ответили, что никто там не видел работу другой команды, а его промпты «никак не могли повлиять на систему».
Заголовок Scientific American о том, что кого-то «обошли», касается Янга — Миллса, задачи из физики. Журнал пишет, что OpenAI, судя по всему, опередила Итана Суссмана, работавшего с Левентом Алпёге из Anthropic, в получении доказательства. Алпёге возразил в X. Всё это не относится к вопросу, работает ли алгоритм для 3-SAT.
Спор вокруг ETH — о процессе. Уильямс назвал один из прежних релизов OpenAI «DDoS-атакой на математиков» (X), а потом согласился помочь с этим. Scientific American пишет, что подход OpenAI к двум из трёх результатов нарушил разъясняющее заявление её же экспертной консультативной группы по ИИ и математике, а промпты и цепочки рассуждений, стоящие за ними, по-прежнему закрыты. В случае с ETH OpenAI согласилась опубликовать доказательство и профинансировать конференцию.
Ломает ли это RSA или шифрование на моём телефоне?
Нет, и не этим путём. Говорим так категорично, потому что причины вполне конкретны. Во-первых, алгоритм решает k-SAT. Фортноу подчёркивает, что он «не даёт ничего нового для задачи о сумме подмножеств и задачи коммивояжёра», потому что при сведении их к 3-SAT число переменных слишком раздувается. Во-вторых, RSA держится на сложности разложения огромного числа на два простых (Financial Times описывает этот метод, не называя его), а это другая задача, нежели выполнение логических формул, и ни один из прочитанных нами источников не говорит, что новый алгоритм до неё дотягивается. В-третьих, оценка асимптотическая: для 2048-битного ключа не меняется ничего ни на одной существующей машине.
Уильямс задал очевидный вопрос научному руководителю OpenAI Дэну Робертсу. Согласно TechCrunch, он спросил, не стало ли что-то небезопасным, и передал, что, по-видимому, в OpenAI это проверили и «достаточно уверены», что взломов из этого не следует. Это информация из вторых рук и неопубликованная, так что взвешивайте её соответственно. Уильямс также сказал, что улучшенный алгоритм мог бы означать, что некоторые размеры ключей придётся считать взломанными.
Под всем этим лежит настоящий открытый вопрос. Уильямс говорит, что «каждому специалисту по computer science, наверное, стоит придавать чуть больше веса правдоподобию P = NP», но Джон Д. Кук замечает, что «статус P = NP по-прежнему неизвестен» (Business Insider). Уильямс также не считает новый алгоритм наилучшим из возможных. Если появится более острый, расклад изменится.
Статья Financial Times — про тренд, а не про это доказательство
Статья FT посвящена растущим математическим способностям ИИ и шифрованию в целом, и в доступной нам части текста ETH не упоминается. Источники там сдержанные. Австралийский математик Джорди Уильямсон сказал аудитории Imperial College, что ИИ вызывает «полную перестройку самого понятия сложности» и что стоит ждать потрясений. Дэниел Шиу из Манчестерского университета назвал взлом шифрования с помощью ИИ «значительным риском» для «более математических форм криптографии», упомянув некоторые «менее зрелые» квантово-устойчивые алгоритмы. Сама FT отмечает, что ИИ «пока не взломал ни один базовый криптографический метод».
Скотт Ааронсон добавил ещё одну нить: криптографии заметно нет в прежнем списке OpenAI из 376 статей, а в обновлении к своему посту он написал, что, по словам его источников, ИИ-компании начали выяснять, могут ли их модели ломать протоколы. Имён он не назвал, и мы тоже не можем.
Наш вывод: разумно беспокоиться о более новых схемах, а не о тех, что работают в вашем браузере. Стандарты NIST 2024 года включают две схемы на решётках и третий стандарт подписи, построенный на другой математике; его держат как запасной вариант на случай, если первые окажутся уязвимыми.
Что на самом деле стоит делать малому бизнесу
Почти ничего, и ничего срочного. Дерево ниже раскладывает по полочкам три ситуации, которые, на наш взгляд, имеют значение.
Одну привычку стоит завести независимо от этой истории. Британский регулятор сказал FT, что компаниям «не стоит откладывать действия» по подготовке к рискам ИИ и квантовых вычислений для криптографии, а BT заявила, что хочет, чтобы её криптографию можно было «менять проще по мере развития стандартов, технологий и угроз». Для небольшой компании это означает: обновляйте софт и спрашивайте у поставщиков, как они будут менять алгоритмы. Вопросы к поставщикам разобраны в нашем фреймворке доверия ИИ-инструментам с вашими данными, а раздел «Безопасность и приватность» в ToolRank перечисляет инструменты по категориям.
Три вещи, которых стоит дождаться, прежде чем говорить «решено»
Следите за тремя вещами. Во-первых, за заключением экспертной группы в составе Импальяццо, Патури и Уильямса и за конференцией, которую OpenAI согласилась профинансировать. Во-вторых, за независимыми прочтениями файлов с формулировками в Lean, ведь именно там может спрятаться тонкая ошибка. И в-третьих, за рецензированием в журнале: пока мы не нашли никаких его признаков. Пока не появится первое из этого, мы говорим «очень вероятно, опровергнута».