То шо нейросети

Опровержения гипотезы экспоненциального времени

Задача 3-SAT — это классическая логическая задача о проверке выполнимости булевых формул в конъюнктивной нормальной форме, где в каждой скобке ровно три переменные. Говоря более простыми словами, задача состоит в поиске такого набора логических значений "истина" или "ложь" для переменных, который сделает истинным все выражение, состоящее из соединённых знаком "И" скобок, где внутри каждой скобки строго три переменные (или их отрицания) объединены знаком "ИЛИ".

Эта задача играет фундаментальную роль в теории сложности алгоритмов как первая доказанная NP-полная задача, к которой можно эффективно свести другие NP-полные задачи. Если для одной из таких задач доказать, что ее можно решить быстро (за полиномиальное время), то это автоматически будет значить, что все такие задачи можно решить быстро.

И вот, только что вышли две работы от OpenAI и Anthropic, которые претендуют на опровержение гипотезы экспоненциального времени (Exponential Time Hypothesis, ETH). Эта гипотеза гласит, что задачу 3-SAT нельзя решить за субэкспоненциальное время в худшем случае. Смысл здесь не в том, что надо обязательно проверить каждую комбинацию. Известные алгоритмы заметно умнее перебора. Гипотеза говорит, что с ростом числа переменных время всё равно должно расти экспоненциально, какие бы мы хитрости ни применяли.

Две вышедшие работы заявляют: ETH ложна. Обе описывают детерминированные алгоритмы не просто для поиска ответа "да" или "нет", а для точного подсчёта всех решений за субэкспоненциальное время. Если можно посчитать решения, можно и проверить, есть ли хотя бы одно. Это не две независимые проверки одного доказательства, а два разных доказательства, каждое из которых еще предстоит проверить, но только одного правильного будет уже достаточно.

Новые алгоритмы, согласно статьям, всё ещё работают очень долго. Их выигрыш перед экспоненциальным временем проявляется асимптотически, на огромных размерах задач. Более того, "субэкспоненциальный" не равно "полиномиальный". То есть гипотеза ETH - это более сильное утверждение, чем "P не равно NP". Поэтому ETH может оказаться ложной, а вопрос P vs NP останется открытым. Из такого ускорения 3-SAT также не следует автоматически столь же быстрое решение каждой задачи класса NP.

→ Если результаты подтвердятся, изменится прежде всего теория. ETH используют как основание условных нижних оценок сложности: "для этой задачи быстрого алгоритма не будет, если верна ETH". Такое основание придётся пересмотреть. Однако это не означает, что появятся быстрые прикладные алгоритмы решения NP-полных задач, которые занимают важное место в самом ИИ. В части ИИ здесь релевантнее то, что при поиске доказательств и формализации использовались ИИ-модели.

Само использование ИИ в математике становится уже рутиной. Так что главное здесь - это потенциальный сдвиг в представлениях о пределах алгоритмов, а не ответ на P vs NP и не новый быстрый SAT-решатель для практики.

https://youtu.be/CWdTBLsbaQs

Говорят OpenAI нашли новое решение для SAT-3 класса задач.

Предложенный алгоритм не просто находит решение задачи, но и позволяет точно определить количество существующих решений.

Работа выглядит убедительно, но на данный момент находится в процессе экспертной проверки. Если доказательство будет верифицировано, это станет одним из самых значимых событий в современной компьютерной науке.