211
правок
Изменения
м
Нет описания правки
{{Определение
|definition=<tex>\mathrm{TQBF}</tex> расшифровывается как '''True Quantified Boolean Formula'''. Это язык верных булевых формул с кванторами.<br/>
<tex>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>.
}}
{{Лемма
|about=1
|statement=<tex>\mathrm{TQBF } \in \mathrm{PS}</tex>.
|proof=Чтобы доказать это, просто приведём программу <tex>solve</tex>, решающую булеву формулу с кванторами на <tex>O(n)</tex> дополнительной памяти и работающую за конечное время.
<tex>solve(Q_1 x_1 Q_2 x_2 \ldots Q_n x_n \phi(x_1, x_2, \ldots, x_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>f(M, w)</tex> оказалась верна, то существует путь из стартовой конфигурации в финишную длины не более, чем <tex>2^{\Omega 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=Доказательство непосредственно следует из лемм.
}}
[[Категория: Теория сложности]]
