PS-полнота языка верных булевых формул с кванторами (TQBF)

2012-06-25T14:54:34Z

217.66.152.161:

{{Определение
|definition=<tex>\mathrm{TQBF}</tex> расшифровывается как '''True Quantified Boolean Formula'''. Это язык верных булевых формул с кванторами.<br/>
<tex>\mathrm{TQBF}=\{Q_1 x_1 Q_2 x_2 \ldots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}</tex>.
}}
{{Определение
|definition=<tex>Quantified Boolean Formula</tex> — это пропозициональная формула с кванторами. Кванторы для каждой переменной записываются в начале выражения.
}}
{{Лемма
|about=1
|statement=<tex>\mathrm{TQBF} \in \mathrm{PS}</tex>.
|proof=Чтобы доказать это, просто приведём программу <tex>solve</tex>, решающую булеву формулу с кванторами на <tex>O(n)</tex> дополнительной памяти и работающую за конечное время.
<tex>solve(k, Q_k x_k \ldots Q_n x_n \phi(x_k, \ldots, x_n))</tex>
'''if''' <tex>k == n</tex>
'''if''' <tex>Q_k = \forall</tex>
'''return''' <tex>\phi(0) \land \phi(1)</tex>
'''if''' <tex>Q_k = \exists</tex>
'''return''' <tex>\phi(0) \lor \phi(1)</tex>
'''if''' <tex>Q_k = \forall</tex>
'''return''' <tex>solve(Q_{k+1} x_{k+1} \ldots Q_n x_n \phi(0, x_{k+1}, \ldots, x_n)) \land solve(Q_{k+1} x_{k+1} \ldots Q_n x_n \phi(1, x_{k+1}, \ldots, x_n))</tex>
'''if''' <tex>Q_k = \exists</tex>
'''return''' <tex>solve(Q_{k+1} x_{k+1} \ldots Q_n x_n \phi(0, x_{k+1}, \ldots, x_n)) \lor solve(Q_{k+1} x_{k+1} \dots Q_n x_n \phi(1, x_{k+1}, \ldots, x_n))</tex>
Эта программа требует <tex>O(n)</tex> дополнительной памяти для хранения стека рекурсивных вызовов. Максимальная глубина стека — <tex>n</tex>.
}}
{{Лемма
|about=2
|statement=<tex>\mathrm{TQBF} \in \mathrm{PSH}</tex>.
|proof=Рассмотрим язык <tex>L \in \mathrm{PS}</tex>.
Построим такую функцию <tex>f</tex>, что <tex>x \in L \Leftrightarrow f(x) \in \mathrm{TQBF}</tex> и <tex>T(f, x) \le p(|x|)</tex>, где <tex>p</tex> — полином.

Так как <tex>L \in \mathrm{PS}</tex>, то существует детерминированная машина Тьюринга <tex>M</tex>, распознающая его с использованием памяти полиномиального размера. Будем считать, что длина ленты машины <tex>M</tex> есть <tex>r(n)</tex>, где <tex>r</tex> — полином, а <tex>n</tex> — длина входа.

Пусть <tex>w = |\Sigma \cup Q|</tex>, <tex>I</tex> — конфигурация <tex>M</tex>. Конфигурация задаётся позицией и содержанием рабочей ленты. Введём обозначение <tex>x_{I,i,c}</tex> — в конфигурации <tex>I</tex> на <tex>i</tex>-том месте стоит символ <tex>c</tex>. Тогда размер конфигурации равен <tex>w r(n)</tex>. Следовательно всего конфигураций <tex>2^{w r(n)}</tex>.

Под выражением <tex>\exists I</tex> будем понимать <tex> \exists x_{I,1,c_1} \, \exists x_{I,1,c_2} \ldots \exists x_{I,1,c_w} \, \exists x_{I,2,c_1} \ldots</tex> Аналогично выражение <tex> \forall I</tex> обозначает <tex> \forall x_{I,1,c_1} \, \forall x_{I,1,c_2} \ldots \forall x_{I,1,c_w} \, \forall x_{I,2,c_1} \ldots</tex>

Рассмотрим функцию <tex>\phi(A, B, t)</tex>, проверяющую следующее условие: конфигурация <tex>B</tex> достижима из конфигурации <tex>A</tex> не более, чем за <tex>2^t</tex> шагов.

<tex>\phi(A, B, 0) = (A = B) \lor (A \vdash B)</tex>.

<tex>\phi(A, B, t) = \exists R \, [\phi(A, R, t-1) \land \phi(R, B, t-1)]</tex>.

Общую длину получившейся формулы можно представить как <tex>L(t) = 2 L(t-1)+const</tex>. Заметим, что из-за умножения на 2 на каждом шаге рекурсии <tex>L(t)</tex> будет иметь экспоненциальный размер относительно <tex>t</tex>. Нас это не устраивает, так как нам необходимо полиномиальное сведение. Поэтому воспользуемся квантором <tex>\forall</tex> и перепишем её следующим образом:

<tex>\phi(A, B, t) = \exists R \,\forall U \,\forall V \, \{\phi(U, V, t-1) \lor \neg [(U = A \land V = R) \lor (U = R \land V = B)]\}</tex>.

Получившаяся в фигурых скобках формула верна только когда верно <tex>\phi(U, V, t-1)</tex> или <tex>\neg[(U = A \land V = R) \lor (U = R \land V = B)]</tex>. Это равносильно тому, что существует такое промежуточное состояние <tex>R</tex>, что <tex>R</tex> достижима из <tex>A</tex> не более, чем за <tex>2^{t-1}</tex> шагов, и <tex>B</tex> достижима из <tex>R</tex> за <tex>2^{t-1}</tex> шагов. А если верно и то, и другое, то конфигурация <tex>B</tex> достижима из конфигурации <tex>A</tex> не более, чем за <tex>2^t</tex> шагов.

За один шаг рекурсии длина максимального пути между конфигурациями уменьшается в два раза. Поэтому общую длину получившейся формулы можно представить как <tex>L(t) = L(t-1)+const</tex>, где <tex>const = \|\exists R \,\forall U \,\forall V \, \{\| + \|\land [(U = A \land V = R) \lor (U = R \land V = B)]\}\|</tex>.
Следовательно, размер полученной функции <tex>\phi(A, B, t)</tex> полиномиален относительно <tex>t</tex>.

Теперь мы можем записать функцию <tex>f(M, w)</tex>, которая будет переводить ДМТ <tex>M</tex> и слово на ленте <tex>w</tex> в формулу из <tex>\mathrm{TQBF}</tex>.

<tex>f(M, w) = \exists S \, \exists F \, (S - start) \land (F - accept) \land \phi(S, F, log_2(2^{w r(n)})))</tex>.

Выражения <tex>S - start</tex> и <tex>F - accept</tex> можно записать следующим образом:

<tex>S - start = x_{S, 1, w[1]} \land x_{S, 2, w[2]} \land \ldots \land x_{S, |w|, w[|w|]} \land x_{S, |w| + 1, B} \ldots \land x_{S, r(n) , B}</tex>.

<tex>F - accept = x_{S, |w| + 1, \#_y} \lor \ldots \lor x_{S, r(n), \#_y}</tex>.

Докажем, что сведение <tex>f</tex> корректно.

Если <tex>w \in L</tex>, то существует путь из стартовой конфигурации в финишную, длины не более, чем <tex>2^{w r(n)}</tex>, а значит формула <tex>f(M, w)</tex> верна.

Если формула <tex>f(M, w)</tex> оказалась верна, то существует путь из стартовой конфигурации в финишную длины не более, чем <tex>2^{w r(n)}</tex>. Значит, ДМТ <tex>M</tex> допускает слово <tex>w</tex>. Тогда <tex>w \in L</tex>.

Таким образом, <tex>\mathrm{TQBF} \in \mathrm{PSH}</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{TQBF} \in \mathrm{PSC}</tex>.
|proof=Доказательство непосредственно следует из лемм.
}}

[[Категория: Теория сложности]]

Викиконспекты - Вклад участника [ru]

PS-полнота языка верных булевых формул с кванторами (TQBF)