Истинная количественная логическая формула - True quantified Boolean formula

В теория сложности вычислений, язык TQBF это формальный язык состоящий из истинные количественные булевы формулы. (Полностью) количественная булева формула - это формула в количественно логика высказываний где каждая переменная определена количественно (или граница ), используя либо экзистенциальный или же универсальный кванторы в начале предложения. Такая формула эквивалентна истинному или ложному (поскольку нет свободный переменные). Если такая формула истинна, то эта формула написана на языке TQBF. Он также известен как QSAT (Количественно СИДЕЛ ).

Обзор

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

{ Displaystyle forall x существует y существует z ((x lor z) земля y)}

QBF - канонический полная проблема за PSPACE, класс задач, решаемых детерминированной или недетерминированной Машина Тьюринга в полиномиальном пространстве и неограниченном времени.^[1] Учитывая формулу в виде абстрактное синтаксическое дерево, проблема может быть легко решена с помощью набора взаимно рекурсивных процедур, которые вычисляют формулу. Такой алгоритм использует пространство, пропорциональное высоте дерева, которое в худшем случае является линейным, но использует экспоненту времени в количестве кванторов.

При условии, что MA ⊊ PSPACE, который широко считается, QBF не может быть решен, и данное решение не может быть даже проверено ни детерминированным, ни вероятностный полиномиальное время (на самом деле, в отличие от проблемы выполнимости, нет известного способа кратко указать решение). Это можно решить с помощью переменная машина Тьюринга за линейное время, поскольку AP = PSPACE, где AP - класс задач, которые переменные машины могут решить за полиномиальное время.^[2]

Когда плодотворный результат IP = Показан PSPACE (см. интерактивная система доказательства ), это было сделано путем демонстрации интерактивной системы доказательства, которая могла решить QBF путем решения определенной арифметизации задачи.^[3]

Формулы QBF имеют ряд полезных канонических форм. Например, можно показать, что существует редукция "много-один" за полиномиальное время это переместит все кванторы на передний план формулы и заставит их чередоваться между универсальными и экзистенциальными кванторами. Есть еще одно сокращение, которое оказалось полезным в доказательстве IP = PSPACE, где не более одного универсального квантификатора помещается между использованием каждой переменной и квантификатором, связывающим эту переменную. Это было критически важно для ограничения количества продуктов в определенных подвыражениях арифметизации.

Prenex нормальная форма

Можно предположить, что полностью количественно определенная логическая формула имеет очень конкретную форму, называемую пренекс нормальная форма. Он состоит из двух основных частей: части, содержащей только квантификаторы, и части, содержащей неквантифицированную логическую формулу, обычно обозначаемую как ${ displaystyle displaystyle phi}$ . Если есть ${ displaystyle displaystyle n}$ Булевы переменные, всю формулу можно записать как

{ displaystyle displaystyle exists x_ {1} forall x_ {2} exists x_ {3} cdots Q_ {n} x_ {n} phi (x_ {1}, x_ {2}, x_ {3}) , точки, x_ {n})}

где каждая переменная попадает в объем некоторого квантификатора. Путем введения фиктивных переменных любую формулу в предваренной нормальной форме можно преобразовать в предложение, в котором чередуются экзистенциальные и универсальные кванторы. Использование фиктивной переменной ${ displaystyle displaystyle y_ {1}}$ ,

{ Displaystyle Displaystyle существует x_ {1} exists x_ {2} phi (x_ {1}, x_ {2}) quad mapsto quad exists x_ {1} forall y_ {1} exists x_ {2} phi (x_ {1}, x_ {2})}

Во втором предложении то же самое значение истины но следует ограниченному синтаксису. Принятие полностью квантифицированных булевых формул в предваренной нормальной форме - частая особенность доказательств.

Решение

Существует простой рекурсивный алгоритм для определения того, находится ли QBF в TQBF (т.е. истинно). Учитывая некоторый QBF

{ Displaystyle Q_ {1} x_ {1} Q_ {2} x_ {2} cdots Q_ {n} x_ {n} phi (x_ {1}, x_ {2}, dots, x_ {n}) .}

Если формула не содержит квантификаторов, мы можем просто вернуть формулу. В противном случае мы снимаем первый квантификатор и проверяем оба возможных значения для первой переменной:

{ displaystyle A = Q_ {2} x_ {2} cdots Q_ {n} x_ {n} phi (0, x_ {2}, dots, x_ {n}),}

{ displaystyle B = Q_ {2} x_ {2} cdots Q_ {n} x_ {n} phi (1, x_ {2}, dots, x_ {n}).}

Если ${ Displaystyle Q_ {1} = существует}$ , затем вернитесь ${ Displaystyle A lor B}$ . Если ${ Displaystyle Q_ {1} = forall}$ , затем вернитесь ${ displaystyle A land B}$ .

Насколько быстро работает этот алгоритм? Для каждого квантификатора в исходной QBF алгоритм выполняет два рекурсивных вызова только для линейно меньшей подзадачи. Это дает алгоритму экспоненциальное время выполнения. O (2^п).

Сколько места занимает этот алгоритм? При каждом вызове алгоритма он должен сохранять промежуточные результаты вычислений A и B. Каждый рекурсивный вызов снимает один квантор, поэтому общая рекурсивная глубина линейна по количеству кванторов. Формулы, в которых отсутствуют кванторы, можно вычислить в пространстве, логарифмическом по количеству переменных. Первоначальный QBF был полностью определен количественно, поэтому количественных показателей было не меньше, чем переменных. Таким образом, этот алгоритм использует О(п + журнал п) = О(п) Космос. Это делает язык TQBF частью PSPACE класс сложности.

PSPACE-полнота

Язык TQBF служит в теория сложности как канонический PSPACE-полный проблема. Полная PSPACE означает, что язык находится в PSPACE и что язык также PSPACE-жесткий. Алгоритм выше показывает, что TQBF находится в PSPACE. Чтобы показать, что TQBF является жестким для PSPACE, необходимо показать, что любой язык в классе сложности PSPACE может быть сокращен до TQBF за полиномиальное время. Т.е.,

{ displaystyle forall L in { mathsf {PSPACE}}, L leq _ {p} mathrm {TQBF}.}

Это означает, что для языка PSPACE L, ввод $Икс$ находится в L, можно определить, проверив, ${ displaystyle f (x)}$ находится в TQBF для некоторой функции $ж$ который требуется для выполнения за полиномиальное время (относительно длины ввода). Символично,

{ displaystyle x in L iff f (x) in mathrm {TQBF}.}

Доказательство того, что TQBF является жестким для PSPACE, требует указания $ж$ .

Итак, предположим, что L - это язык PSPACE. Это означает, что L может быть определено детерминированным полиномиальным пространством. Машина Тьюринга (DTM). Это очень важно для сокращения L до TQBF, потому что конфигурации любой такой машины Тьюринга могут быть представлены в виде булевых формул с логическими переменными, представляющими состояние машины, а также содержимое каждой ячейки на ленте машины Тьюринга, с позицией головы машины Тьюринга, закодированной в формуле по порядку формулы. В частности, наша редукция будет использовать переменные ${ displaystyle c_ {1}}$ и ${ displaystyle c_ {2}}$ , которые представляют две возможные конфигурации DTM для L и натурального числа t, при построении QBF ${ displaystyle phi _ {c_ {1}, c_ {2}, t}}$ что верно тогда и только тогда, когда DTM для L может исходить из конфигурации, закодированной в ${ displaystyle c_ {1}}$ к конфигурации, закодированной в ${ displaystyle c_ {2}}$ не более чем за t шагов. Функция $ж$ , то построим из ЦММ для L QBF ${ displaystyle phi _ {c_ {start}, c_ {accept}, T}}$ , куда ${ displaystyle c_ {start}}$ стартовая конфигурация DTM, ${ displaystyle c_ {accept}}$ - принимающая конфигурация DTM, а T - максимальное количество шагов, которое может потребоваться DTM для перехода от одной конфигурации к другой. Мы знаем это Т = О(ехр (п)), где n - длина входных данных, поскольку это ограничивает общее количество возможных конфигураций соответствующего DTM. Конечно, для DTM не может быть больше шагов, чем возможных конфигураций для достижения ${ displaystyle c _ { mathrm {accept}}}$ если он не входит в цикл, и в этом случае он никогда не достигнет ${ displaystyle c _ { mathrm {accept}}}$ так или иначе.

На этом этапе доказательства мы уже снизили вопрос о том, является ли входная формула $ш$ (закодировано, конечно, в ${ displaystyle c_ {start}}$ ) принадлежит L к вопросу о том, является ли QBF ${ displaystyle phi _ {c_ {start}, c_ {accept}, T}}$ , т.е. ${ displaystyle f (w)}$ , находится в TQBF. Остальная часть этого доказательства доказывает, что $ж$ можно вычислить за полиномиальное время.

За ${ displaystyle t = 1}$ , вычисление ${ displaystyle phi _ {c_ {1}, c_ {2}, t}}$ прост - либо одна из конфигураций меняется за один шаг, либо нет. Поскольку машина Тьюринга, которую представляет наша формула, является детерминированной, это не представляет проблемы.

За ${ displaystyle t> 1}$ , вычисление ${ displaystyle phi _ {c_ {1}, c_ {2}, t}}$ включает рекурсивную оценку, ищущую так называемую "среднюю точку" ${ displaystyle m_ {1}}$ . В этом случае перепишем формулу следующим образом:

{ displaystyle phi _ {c_ {1}, c_ {2}, t} = exists m_ {1} ( phi _ {c_ {1}, m_ {1}, lceil t / 2 rceil} клин phi _ {m_ {1}, c_ {2}, lceil t / 2 rceil}).}

Это меняет вопрос о том, ${ displaystyle c_ {1}}$ может достигать ${ displaystyle c_ {2}}$ за t шагов к вопросу о том, ${ displaystyle c_ {1}}$ достигает средней точки ${ displaystyle m_ {1}}$ в ${ displaystyle t / 2}$ шагов, который сам достигает ${ displaystyle c_ {2}}$ в ${ displaystyle t / 2}$ шаги. Ответ на последний вопрос, конечно же, дает ответ на первый.

Теперь t ограничено только T, которое экспоненциально (а значит, не полиномиально) по длине ввода. Кроме того, каждый рекурсивный слой практически удваивает длину формулы. (Переменная ${ displaystyle m_ {1}}$ это только одна середина - для большего t по пути будет больше остановок, так сказать.) Итак, время, необходимое для рекурсивной оценки ${ displaystyle phi _ {c_ {1}, c_ {2}, t}}$ таким образом, тоже может быть экспоненциальным, просто потому, что формула может стать экспоненциально большой. Эта проблема решается путем универсального количественного определения с использованием переменных ${ displaystyle c_ {3}}$ и ${ displaystyle c_ {4}}$ по парам конфигураций (например, ${ Displaystyle {(c_ {1}, m_ {1}), (m_ {1}, c_ {2}) }}$ ), что предотвращает увеличение длины формулы за счет рекурсивных слоев. Это дает следующую интерпретацию ${ displaystyle phi _ {c_ {1}, c_ {2}, t}}$ :

{ displaystyle phi _ {c_ {1}, c_ {2}, t} = exists m_ {1} forall (c_ {3}, c_ {4}) in {(c_ {1}, m_ {1}), (m_ {1}, c_ {2}) } ( phi _ {c_ {3}, c_ {4}, lceil t / 2 rceil}).}

Эта версия формулы действительно может быть вычислена за полиномиальное время, поскольку любой ее экземпляр может быть вычислен за полиномиальное время. Универсально определенная упорядоченная пара просто говорит нам, что какой бы выбор ${ displaystyle (c_ {3}, c_ {4})}$ сделан, ${ Displaystyle phi _ {c_ {1}, c_ {2}, t} iff phi _ {c_ {3}, c_ {4}, lceil t / 2 rceil}}$ .

Таким образом, ${ displaystyle forall L in { mathsf {PSPACE}}, L leq _ {p} mathrm {TQBF}}$ , поэтому TQBF сложен для PSPACE. Вместе с приведенным выше результатом, что TQBF находится в PSPACE, это завершает доказательство того, что TQBF является PSPACE-полным языком.

(Это доказательство следует за Sipser 2006 pp. 310–313 во всем существенном. Papadimitriou 1994 также включает доказательство.)

Разное

Одна из важных подзадач в TQBF - это Проблема логической выполнимости. В этой задаче вы хотите знать, является ли данная логическая формула ${ displaystyle phi}$ может быть выполнено с помощью некоторого присвоения переменных. Это эквивалентно TQBF с использованием только квантификаторов существования:

{ Displaystyle существует x_ {1} cdots exists x_ {n} phi (x_ {1}, ldots, x_ {n})}

Это также пример большего результата NP

{ displaystyle substeq}

PSPACE, который следует непосредственно из наблюдения, что средство проверки полиномиального времени для доказательства языка, принятого NTM (Недетерминированная машина Тьюринга ) требует полиномиального пространства для хранения доказательства.

Любой класс в полиномиальная иерархия (PH ) TQBF представляет собой серьезную проблему. Другими словами, для класса, включающего все языки L, для которых существует поли-временный TM V, верификатор, такой, что для всех входных x и некоторой константы i,

{ displaystyle x in L Leftrightarrow exists y_ {1} forall y_ {2} cdots Q_ {i} y_ {i} V (x, y_ {1}, y_ {2}, dots, y_ {i}) = 1}

который имеет конкретную формулировку QBF, которая задается как

{ Displaystyle существует phi}

такой, что

{ displaystyle exists { vec {x_ {1}}} forall { vec {x_ {2}}} cdots Q_ {i} { vec {x_ {i}}} phi ({ vec {x_ {1}}}, { vec {x_ {2}}}, dots, { vec {x_ {i}}}) = 1}

где

{ displaystyle { vec {x_ {i}}}}

's - векторы булевых переменных.

Важно отметить, что хотя язык TQBF определен как набор истинных количественных логических формул, аббревиатура TQBF часто используется (даже в этой статье) для обозначения полностью количественной логической формулы, часто называемой просто QBF (количественная логическая формула, понимаемая как «полностью» или «полностью» определенная количественно). Важно различать контекстуально два использования аббревиатуры TQBF при чтении литературы.
TQBF можно рассматривать как игру между двумя игроками с чередованием ходов. Переменные, определяемые количественно, эквивалентны представлению о том, что игрок может сделать ход в свой ход. Универсальные количественные переменные означают, что исход игры не зависит от того, какой ход игрок делает в этот ход. Кроме того, TQBF, первый квантор которого является экзистенциальным, соответствует формула игры в которой у первого игрока есть выигрышная стратегия.
TQBF, для которого количественная формула находится в 2-CNF может быть решено в линейное время, по алгоритму, включающему надежный анализ связности своего граф импликации. В 2-выполнимость проблема является частным случаем TQBF для этих формул, в котором каждый квантор экзистенциальный.^[4]^[5]
Существует систематическая обработка ограниченных версий количественных булевых формул (дающих классификации типа Шефера), представленная в пояснительной статье Хуби Чена.^[6]
Планарный TQBF, обобщающий Планар SAT, был доказан Д. Лихтенштейном PSPACE-полным.^[7]

Примечания и ссылки

^ М. Гарей и Д. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. В. Х. Фриман, Сан-Франциско, Калифорния. ISBN 0-7167-1045-5.
^ А. Чандра, Д. Козен и Л. Штокмейер (1981). «Чередование». Журнал ACM. 28 (1): 114–133. Дои:10.1145/322234.322243.CS1 maint: несколько имен: список авторов (связь)
^ Ади Шамир (1992). «Ip = Pspace». Журнал ACM. 39 (4): 869–877. Дои:10.1145/146585.146609.
^ Кром, Мелвен Р. (1967). «Проблема решения для класса формул первого порядка, в котором все дизъюнкции двоичны». Zeitschrift für Mathematische Logik und Grundlagen der Mathematik. 13 (1–2): 15–20. Дои:10.1002 / malq.19670130104..
^ Аспвалл, Бенгт; Plass, Майкл Ф .; Тарджан, Роберт Э. (1979). «Алгоритм линейного времени для проверки истинности определенных количественных булевых формул» (PDF). Письма об обработке информации. 8 (3): 121–123. Дои:10.1016/0020-0190(79)90002-4..
^ Чен, Хуби (декабрь 2009 г.). «Встреча логики, сложности и алгебры». Опросы ACM Computing. ACM. 42 (1): 1–32. arXiv:cs / 0611018. Дои:10.1145/1592451.1592453.
^ Лихтенштейн, Дэвид (1982-05-01). «Планарные формулы и их использование». SIAM Журнал по вычислениям. 11 (2): 329–343. Дои:10.1137/0211025. ISSN 0097-5397.

Fortnow & Homer (2003) дает некоторую историческую справку о PSPACE и TQBF.
Чжан (2003) дает некоторую историческую справку о булевых формулах.
Арора, Санджив. (2001). COS 522: вычислительная сложность. Конспект лекций, Принстонский университет. Проверено 10 октября 2005 года.
Фортноу, Лэнс и Стив Гомер. (2003, июнь). Краткая история вычислительной сложности. Колонка вычислительной сложности, 80. Проверено 9 октября 2005 г.
Пападимитриу, К. Х. (1994). Вычислительная сложность. Читает: Эддисон-Уэсли.
Сипсер, Майкл. (2006). Введение в теорию вычислений. Бостон: Технология курса Thomson.
Чжан, Линтао. (2003). В поисках истины: методы выполнимости булевых формул. Проверено 10 октября 2005 года.

Смотрите также

Теорема Кука – Левина, заявив, что СИДЕЛ является НП-полный
Обобщенная география

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

Библиотека количественных булевых формул (QBFLIB)
Международный семинар по количественным булевым формулам
DepQBF - решатель на основе поиска для количественных булевых формул
CAQE - решатель на основе CEGAR для количественных булевых формул; победитель последних выпусков ежегодного конкурса решателей QBF QBFEVAL.
КАДЕТ - решатель для количественных булевых формул, ограниченный одним чередованием кванторов, с возможностью вычисления Сколемские функции

[1] М. Гарей и Д. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. В. Х. Фриман, Сан-Франциско, Калифорния. ISBN 0-7167-1045-5.

[2] А. Чандра, Д. Козен и Л. Штокмейер (1981). «Чередование». Журнал ACM. 28 (1): 114–133. Дои:10.1145/322234.322243.CS1 maint: несколько имен: список авторов (связь)

[3] Ади Шамир (1992). «Ip = Pspace». Журнал ACM. 39 (4): 869–877. Дои:10.1145/146585.146609.

[4] Кром, Мелвен Р. (1967). «Проблема решения для класса формул первого порядка, в котором все дизъюнкции двоичны». Zeitschrift für Mathematische Logik und Grundlagen der Mathematik. 13 (1–2): 15–20. Дои:10.1002 / malq.19670130104..

[5] Аспвалл, Бенгт; Plass, Майкл Ф .; Тарджан, Роберт Э. (1979). «Алгоритм линейного времени для проверки истинности определенных количественных булевых формул» (PDF). Письма об обработке информации. 8 (3): 121–123. Дои:10.1016/0020-0190(79)90002-4..

[6] Чен, Хуби (декабрь 2009 г.). «Встреча логики, сложности и алгебры». Опросы ACM Computing. ACM. 42 (1): 1–32. arXiv:cs / 0611018. Дои:10.1145/1592451.1592453.

[7] Лихтенштейн, Дэвид (1982-05-01). «Планарные формулы и их использование». SIAM Журнал по вычислениям. 11 (2): 329–343. Дои:10.1137/0211025. ISSN 0097-5397.

[1]

[2]

[3]

[4]

[5]

[6]

[7]