Теория сложности доказательств

Теория сложности доказательств — это раздел математической логики и теоретической информатики, изучающий ресурсные затраты (время, память, длину) на установление истинности математических утверждений в формальных системах. В отличие от классической теории сложности вычислений, которая исследует сложность решения задач, теория сложности доказательств фокусируется на сложности обоснования правильности решений. Она отвечает на вопрос: насколько длинным или сложным должно быть доказательство, чтобы убедить проверяющего в истинности некоторого утверждения, и можно ли найти короткое доказательство для любого истинного утверждения.

История

Истоки теории сложности доказательств лежат в работах начала XX века, связанных с основаниями математики. В 1930-х годах Курт Гёдель доказал теоремы о неполноте, показав, что в любой достаточно мощной формальной системе существуют истинные, но недоказуемые утверждения. Однако вопрос о том, насколько длинными могут быть доказательства для доказуемых утверждений, оставался открытым.

В 1970-х годах, с развитием теории сложности вычислений, Стивен Кук и Роберт Рекхоу независимо сформулировали проблему существования коротких доказательств. Кук в 1971 году ввел класс NP (задачи, решение которых можно проверить за полиномиальное время), а Рекхоу в 1975 году показал, что существование полиномиально ограниченных доказательств для всех тавтологий эквивалентно равенству классов NP и co-NP. Это стало ключевым моментом, связавшим теорию сложности доказательств с фундаментальными вопросами теории сложности.

В 1980-х годах началось систематическое изучение конкретных систем доказательств. Были введены понятия пропозициональных систем доказательств, таких как резолюция, система Фреге и система на основе таблиц. В 1990-х годах были получены первые нижние оценки длины доказательств для некоторых систем, в частности, для резолюции (Алон, Бен-Сассон, Иммерман и другие). В 2000-х годах внимание сместилось к более мощным системам, таким как системы с ограниченным использованием аксиом и системы на основе алгебраических методов.

Основные понятия

Формальная система и доказательство

Формальная система состоит из:

• Алфавита — конечного набора символов.
• Грамматики — правил построения формул.
• Аксиом — исходных формул, принимаемых без доказательства.
• Правил вывода — правил, позволяющих из одних формул получать другие.

Доказательство в формальной системе — это конечная последовательность формул, каждая из которых является либо аксиомой, либо получена из предыдущих формул по правилам вывода. Последняя формула последовательности называется доказываемым утверждением.

Пропозициональные системы доказательств

Наиболее изученным классом являются пропозициональные системы доказательств, где утверждения представляют собой формулы логики высказываний. Основные системы включают:

• Резолюция — система, основанная на правиле резолюции: из двух дизъюнктов (A ∨ B) и (¬A ∨ C) выводится (B ∨ C). Широко используется в автоматическом доказательстве теорем.
• Система Фреге — классическая система, использующая аксиомы и правила modus ponens и подстановки. Обычно рассматривается с фиксированным набором логических связок (например, ¬, ∧, ∨, →).
• Система на основе таблиц — метод, основанный на построении таблиц истинности или семантических деревьев.
• Системы с ограниченным использованием аксиом — например, системы, где разрешено использовать только аксиомы определенного вида (например, только аксиомы равенства или только аксиомы арифметики).

Длина доказательства и сложность

Длина доказательства — это количество формул в последовательности. Сложность доказательства может измеряться не только длиной, но и размером (количеством символов) или глубиной (максимальной длиной пути в дереве вывода). Для практических приложений важна асимптотическая сложность: как растет длина доказательства в зависимости от размера исходной формулы.

Классы сложности доказательств

Класс NP и co-NP

Класс NP включает задачи, для которых существует полиномиально ограниченное доказательство (сертификат) правильности решения. Например, задача выполнимости булевой формулы (SAT) является NP-полной: если формула выполнима, то существует короткое доказательство (набор значений переменных). Класс co-NP включает задачи, для которых существует полиномиально ограниченное доказательство ложности. Например, задача тавтологии (является ли формула тождественно истинной) принадлежит co-NP.

Связь с теорией сложности доказательств: существование полиномиально ограниченной системы доказательств для всех тавтологий эквивалентно равенству классов NP и co-NP. Это одна из центральных нерешенных проблем теории сложности.

Класс P и NP-полнота

Класс P включает задачи, решаемые за полиномиальное время. Если бы существовала полиномиально ограниченная система доказательств для всех тавтологий, то это означало бы, что задача проверки тавтологии (co-NP-полная) решается за полиномиальное время, что маловероятно. Поэтому большинство исследователей полагают, что NP ≠ co-NP, и, следовательно, не существует универсальной полиномиально ограниченной системы доказательств.

Нижние оценки и результаты

Нижние оценки для резолюции

Одним из первых значительных результатов стало получение экспоненциальных нижних оценок для резолюции. В 1985 году Алон, Бен-Сассон и Иммерман доказали, что для некоторых формул (например, принципа Дирихле) любое резолюционное доказательство имеет экспоненциальную длину. Это показало, что резолюция не является универсально эффективной системой.

Нижние оценки для систем Фреге

Для систем Фреге нижние оценки остаются открытой проблемой. Известно, что существуют формулы, для которых доказательства в системе Фреге имеют полиномиальную длину, но неизвестно, существуют ли формулы, требующие экспоненциальной длины. Считается, что такие формулы существуют, но доказательство этого потребует решения фундаментальных проблем теории сложности.

Теорема о неполноте и сложность

Теорема Гёделя о неполноте имеет прямое отношение к сложности доказательств: она утверждает, что в любой достаточно мощной формальной системе существуют истинные, но недоказуемые утверждения. Однако для пропозициональных систем, которые не содержат арифметики, таких утверждений нет — все тавтологии доказуемы. Вопрос лишь в длине доказательства.

Применение

Автоматическое доказательство теорем

Теория сложности доказательств лежит в основе алгоритмов автоматического доказательства теорем. Системы, основанные на резолюции, используются в таких программах, как Vampire, E Prover и SPASS. Понимание сложности доказательств позволяет разрабатывать более эффективные стратегии поиска.

Криптография

В криптографии теория сложности доказательств используется для анализа безопасности протоколов. Например, системы доказательств с нулевым разглашением (zero-knowledge proofs) основаны на идее, что доказательство может быть коротким и не раскрывать никакой информации, кроме самого факта истинности утверждения. Сложность таких доказательств изучается в рамках теории сложности доказательств.

Теория баз данных

В теории баз данных сложность доказательств применяется для анализа сложности запросов. Например, задача проверки выполнимости запроса к реляционной базе данных может быть сведена к задаче проверки тавтологии в логике первого порядка. Теория сложности доказательств позволяет оценить, насколько сложно проверить корректность запроса.

Открытые проблемы

• Равенство NP и co-NP: является ли класс NP равным co-NP? Если да, то существуют полиномиально ограниченные системы доказательств для всех тавтологий. Если нет, то такие системы невозможны.
• Нижние оценки для систем Фреге: существуют ли формулы, для которых доказательства в системе Фреге имеют экспоненциальную длину? Это одна из самых сложных проблем в области.
• Сложность доказательств в арифметике Пеано: насколько длинными могут быть доказательства в арифметике Пеано для утверждений, которые недоказуемы в более слабых системах? Это связано с теоремой Гёделя и проблемой неполноты.

Интересные факты

• Теория сложности доказательств тесно связана с проблемой P vs NP, одной из семи «задач тысячелетия» Института Клэя. Если P = NP, то все задачи, проверяемые за полиномиальное время, решаются за полиномиальное время, что имело бы огромные последствия для теории сложности доказательств.
• В 1990-х годах было показано, что для некоторых систем доказательств (например, резолюции) существуют экспоненциальные нижние оценки, но для других (например, систем Фреге) такие оценки неизвестны. Это создает иерархию сложности систем доказательств.
• Теория сложности доказательств находит применение в теории игр и искусственном интеллекте, где она используется для анализа сложности стратегий и обучения.

Источники

• Алон Н., Бен-Сассон Э., Иммерман Н. «Нижние оценки для резолюции». Journal of the ACM, 1985.
• Кук С. «Сложность процедур доказательства теорем». Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971.
• Рекхоу Р. «О сложности доказательств в формальных системах». Journal of Symbolic Logic, 1975.
• Гёдель К. «О формально неразрешимых предложениях Principia Mathematica и родственных систем». 1931.
• Уркварт А. «Сложность доказательств: обзор». Bulletin of the EATCS, 1995.