OpenAI опроверг гипотезу экспоненциального времени, что это значит

Как пишет TechCrunch, компания OpenAI накануне представила решения трех значительных математических задач, которые долгое время вызывали затруднения у исследователей. Одним из сюрпризов стало опровержение гипотезы экспоненциального времени (ETH), которая является устойчивым предположением в информатике и играет важную роль в нашем понимании сложности вычислений. Как и в случае с предыдущими публикациями от лаборатории, научные сообщества отреагировали с сочетанием восторга и тревоги. Математик компании Anthropic Левент Альпёге предположил, что OpenAI основывает свои решения на уже существующих работах, а спустя несколько часов Anthropic выпустила собственное опровержение ETH. Тем не менее, процесс работы OpenAI эволюционирует. На этот раз лаборатория структурировала свои публикации по-разному для каждой из трех задействованных дисциплин: математики получили материалы на GitHub; компьютерные ученые сформировали рабочую группу, попросили о публичном распространении доказательств и о финансировании конференции для их обсуждения; физики также создали рабочую группу, которая определит, как будет представлено их исследование. Профессор MIT Райан Уильямс, который организует ответ своей области на новое открытие, ранее критиковал подход OpenAI, назвав его публикацию доказательств в начале октября «DDOS-атакой на математиков». Однако он согласился сотрудничать с лабораториями, чтобы помочь сформулировать идеи, важные для области, как он сообщил TechCrunch. Лаборатория попросила его помочь интерпретировать решение вместе с компьютерными учеными из Университета Калифорнии в Сан-Диего Расселом Импальяццо и Рамамоханом Патури, которые впервые опубликовали ETH в 1999 году. Их первым шагом стало публикация открытого письма с призывом к ученым, заинтересованным в этих вопросах, обсудить нормы, касающиеся вклада ИИ в их работу. «Некоторые части [доказательства OpenAI] можно назвать, возможно, рутинными, но да, есть две или три части, которые выглядят чуждыми, и именно эти части заставили меня подумать, что сообществу нужно работать над ними вместе», — сказал Уильямс. ETH является частью более широкой категории проблем, известных как P против NP, которые волнуют информатику и многие другие области на протяжении десятилетий. Упрощенно, исследователи пытаются понять, может ли любая проблема, решение которой можно легко проверить (NP), также быть легко решаемой (P). Простой пример — игра Судоку: как только решение головоломки найдено, его можно быстро проверить, но найти его занимает много времени. Эта динамика актуальна для множества важных задач, и это понимание лежит в основе криптографических систем: когда у вас есть ключ к зашифрованному сообщению, вы можете его расшифровать, но на самом деле взлом эффективного кода занимает слишком много времени, чтобы быть полезным. Однако ученые до сих пор не доказали, всегда ли это так. «P = NP означает, что не только вы можете проверять решения Судоку, когда они существуют, но и просто генерировать их», — сказал Уильямс. «P = NP утверждает, что это верно для каждой проблемы, которую вы можете быстро проверить — если вы можете быстро проверить, вы можете быстро решить. Так что это кажется слишком хорошим, чтобы быть правдой». Вот почему большинство ученых предполагают, что P ≠ NP. ETH предоставила доказательства этого. Она в основном утверждает, что даже самый быстрый алгоритм компьютера требует экспоненциально больше времени для нахождения решения по мере увеличения числа переменных в определенном классе сложных логических задач. Заявления OpenAI и Anthropic заключаются в том, что их модели разработали алгоритмы, которые решают эти задачи за «подэкспоненциальное» время, что означает быстрее, чем считалось возможным ранее. Если это правда, они могут доказать, что EFT ложна — опровергли ее, с научной точки зрения — и возможно открыли путь для алгоритмов, которые в целом работают по принципу P = NP. «Каждому компьютерному ученому, вероятно, стоит уделить больше внимания правдоподобности P = NP, но вес может варьироваться», — сказал Уильямс. «Я действительно думаю, что это ставит под сомнение многие интуиции, которые у нас были о том, насколько разрешимы [сложные NP-проблемы]. Я также думаю, что это, вероятно, не окончательный ответ. Я не думаю, что алгоритм OpenAI может быть лучшим, который вы можете получить». Работа впереди для компьютерных ученых. Устойчивость ETH привела к тому, что она была включена во множество научных работ за последнее десятилетие, которые придется пересмотреть, если утверждения лабораторий ИИ о том, что они опровергли ее, подтвердятся. «Именно поэтому я просил или настаивал на том, чтобы OpenAI поддержала конференцию по этому вопросу — это повлияет на работы многих исследователей, и нам нужно понять, что будет дальше, помимо понимания алгоритмов. Нам нужно понять, как должны изменяться основы по сравнению с тем, что у нас было раньше», — сказал он. Перед научными вопросами стоят вопросы кибербезопасности. Уильямс отметил, что улучшенный алгоритм может означать, что криптографические системы, полагающиеся на определенные размеры ключей, могут быть признаны сломанными. Таким образом, один из первых вопросов, который он задал научному руководителю OpenAI Дэну Робертсу, заключался в том, проверили ли они, затрагивает ли это какие-либо криптосистемы... безопасно ли что-либо сейчас? И, как оказалось, они проверили и были уверены, что это не подразумевает никаких уязвимостей. Эта новая парадигма ИИ в научных открытиях все еще находится в процессе разработки, но Уильямс говорит, что он оптимистичен, несмотря на реальные опасения, особенно по поводу подготовки следующего поколения ученых. Будучи компьютерным ученым, занимающимся высокоуровневой математикой, он, возможно, легче адаптировался к изменениям, чем чистые математики. Тем не менее, он говорит, что ИИ «заставляет людей быть немного более амбициозными в том, какой вид работы они делают, и глубже думать о том, если все, над чем я раньше работал, теперь является легкой добычей для ИИ, как я могу поднять планку для научных вопросов, которые я хочу задавать?» Материал подготовлен нейросетью на основе оригинальной публикации. ИИ может ошибаться в деталях (цифры, имена, даты, цитаты) — для важной информации сверяйтесь с первоисточником.