211
правок
Изменения
м
Нет описания правки
{{Определение
|definition=<tex>TQBF</tex> расшифровывается как True Quantified Boolean Formula. Это язык верных булевых формул с кванторами.
<tex>TQBF=\{Q_1 x_1 Q_2 x_2 \cdots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}</tex>.
}}
Чтобы доказать, что <tex>TQBF \in \mathrm{PSC}</tex>, необходимо показать, что <tex>TQBF \in \mathrm{PSH}</tex> и <tex>TQBF \in \mathrm{PS}</tex>.
{{Лемма
|about=1
|statement=<tex>TQBF \in \mathrm{PS}</tex>.
|proof=Чтобы доказать это, просто приведём программу <tex>solve</tex>, решающую булеву формулу с кванторами на <tex>O(n)</tex> дополнительной памяти и работающую за конечное время.
<tex>solve(Q_1 x_1 Q_2 x_2 \cdots Q_n x_n \phi(x_1, x_2, \dots, x_n))</tex>
