68
правок
Изменения
Новая страница: «{{Определение |definition=<tex>TQBF</tex> расшивровывается как True Quantified Boolean Formula. Это язык верных бул...»
{{Определение
|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 PS-complete</tex> необходимо показать что:
{{Лемма
|about=1
|statement=<tex>TQBF \in PS</tex>
|proof=
}}
{{Лемма
|about=2
|statement=<tex> \forall L \in PS \Rightarrow L \leq_p TQBF</tex>
|proof=
}}
|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 PS-complete</tex> необходимо показать что:
{{Лемма
|about=1
|statement=<tex>TQBF \in PS</tex>
|proof=
}}
{{Лемма
|about=2
|statement=<tex> \forall L \in PS \Rightarrow L \leq_p TQBF</tex>
|proof=
}}
