Система пропозициональных доказательств - Propositional proof system

В пропозициональное исчисление и сложность доказательства а пропозициональная система доказательства (pps), также называемый Система пропозициональных доказательств Кука – Рекхоу, это система для доказательства классический пропозициональный тавтологии.

Математическое определение

Формально pps - это полиномиальное время функция п чей классифицировать есть множество всех пропозициональных тавтологий (обозначаемых TAUT).^[1] Если А формула, то любая Икс такой, что п(Икс) = А называется п-доказательство чего-либо А. Условие, определяющее pps, можно разбить следующим образом:

Полнота: каждый пропозициональный тавтология имеет п-доказательство,
Разумность: если пропозициональная формула имеет п- доказано, то это тавтология,
Эффективность: п вбегает полиномиальное время.

В общем, система доказательств для языка L - функция полиномиального времени, диапазон которой равен L. Таким образом, пропозициональная система доказательств является системой доказательств для TAUT.

Иногда рассматривается следующее альтернативное определение: pps задается как алгоритм проверки-доказательства. п(А,Икс) с двумя входами. Если п принимает пару (А,Икс) мы говорим, что Икс это п-доказательство чего-либо А. п требуется, чтобы работать за полиномиальное время, и, кроме того, он должен иметь А имеет п-устойчивость тогда и только тогда, когда это тавтология.

Если п₁ является pps согласно первому определению, то п₂ определяется п₂(А,Икс) если и только если п₁(Икс) = А является pps согласно второму определению. Наоборот, если п₂ является pps согласно второму определению, то п₁ определяется

{ displaystyle P_ {1} ( langle x, A rangle) = { begin {cases} A & { text {if}} P_ {2} (A, x) top & { text {иначе }} end {case}}}

(п₁ принимает пары в качестве входных данных) является pps согласно первому определению, где ${ displaystyle top}$ фиксированная тавтология.

Алгоритмическая интерпретация

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

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

История

Исторически, Исчисление высказываний Фреге была первой пропозициональной системой доказательства. Общее определение пропозициональной системы доказательств связано с Стивен Кук и Роберт А. Рекхоу (1979).^[1]

Связь с теорией сложности вычислений

Систему пропозициональных доказательств можно сравнить с помощью понятия p-симуляция. Система пропозициональных доказательств п р-имитирует Q (написано как п ≤_пQ) при наличии полиномиальной функции F такой, что п(F(Икс)) = Q(Икс) для каждого Икс.^[1] То есть, учитывая Q-доказательство Икс, мы можем найти за полиномиальное время a п-доказательство той же тавтологии. Если п ≤_пQ и Q ≤_пп, системы доказательства п и Q находятся p-эквивалент. Существует также более слабое понятие моделирования: pps п имитирует или же слабо p-моделирует Программы Q если есть многочлен п так что для каждого Q-доказательство Икс тавтологии А, Существует п-доказательство у из А так что длина у, |у| самое большее п(|Икс|). (Некоторые авторы используют слова p-имитация и симуляция как синонимы для любого из этих двух понятий, обычно последнего.)

Система пропозициональных доказательств называется p-оптимальный если оно п-моделирует все другие пропозициональные системы доказательства, и это оптимальный если он имитирует все остальные pps. Система пропозициональных доказательств п является полиномиально ограниченный (также называемый супер), если каждая тавтология имеет короткий (т.е.полиномиальный размер) п-доказательство.

Если п полиномиально ограничена и Q имитирует п, тогда Q также полиномиально ограничена.

Набор пропозициональных тавтологий, TAUT, является coNP -полный комплект. Система пропозиционального доказательства - это средство проверки сертификата членства в TAUT. Существование полиномиально ограниченной системы пропозициональных доказательств означает, что существует верификатор с сертификатами полиномиального размера, т. Е. TAUT находится в НП. На самом деле эти два утверждения эквивалентны, т.е. существует полиномиально ограниченная пропозициональная система доказательств тогда и только тогда, когда классы сложности NP и coNP равны.^[1]

Некоторые классы эквивалентности симулируемых систем доказательств или п-имуляторы тесно связаны с теориями ограниченная арифметика; по сути, они являются «неоднородными» версиями ограниченной арифметики, точно так же, как классы схем являются неоднородными версиями классов сложности на основе ресурсов. «Расширенные системы Фреге» (допускающие введение новых переменных по определению) соответствуют таким образом, например, полиномиально-ограниченным системам. Там, где ограниченная арифметика, в свою очередь, соответствует классу сложности, основанному на схемах, часто есть сходства между теорией систем доказательства и теорией семейств схем, такие как сопоставление результатов с нижней оценкой и разделения. Например, точно так же, как подсчет не может выполняться ${ displaystyle mathbf {AC} ^ {0}}$ семейство схем субэкспоненциального размера, многие тавтологии, относящиеся к принцип голубятни не может иметь субэкспоненциальных доказательств в системе доказательств, основанной на формулах ограниченной глубины (и, в частности, не на системах, основанных на разрешении, так как они полагаются только на формулы глубины 1).

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

Связь между некоторыми общими системами доказательства

Вот некоторые примеры изученных пропозициональных систем доказательства:

Пропозициональный Разрешение и различные ограничения и расширения, такие как Алгоритм DPLL
Естественный вычет
Последовательное исчисление
Система Фреге
Расширенная система Фреге
Полиномиальное исчисление
Система Nullstellensatz
Режущий метод

дальнейшее чтение

Сэмюэл Басс (1998), "Введение в теорию доказательств", в: Справочник по теории доказательств (под ред. С.Р. Бусса), Elsevier (1998).
П. Пудлак (1998 г.) "Длина доказательств ", в: Справочник по теории доказательств (изд. С.Р. Бусс), Elsevier, (1998).
П. Бим и Т. Питасси (1998). Сложность пропозиционального доказательства: прошлое, настоящее и будущее. Технический отчет TR98-067, Электронный коллоквиум по вычислительной сложности.
Натан Сегерлинд (2007) «Сложность пропозициональных доказательств», Бюллетень символической логики 13 (4): 417–481
Я. Крайичек (1995), Ограниченная арифметика, логика высказываний и теория сложности, Издательство Кембриджского университета.
Я. Крайичек, Сложность доказательства, в: Учеб. 4-й Европейский математический конгресс (под ред. А. Лаптева), EMS, Цюрих, стр. 221–231, (2005).
Я. Крайичек, Сложность пропозиционального доказательства I. и Сложность доказательства и арифметика.
Стивен Кук и Фыонг Нгуен, Логические основы сложности доказательства, Cambridge University Press, 2010 (проект от 2008 г. )
Роберт Реккау, О длине доказательств в исчислении высказываний, Кандидатская диссертация, 1975.

внешняя ссылка

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

[cr-1] а ^б ^c ^d Повар, Стивен; Рекхоу, Роберт А. (1979). «Относительная эффективность пропозициональных систем доказательства». Журнал символической логики. 44 (1). С. 36–50. JSTOR 2273702.

[1]