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

Материал из Викиконспекты
Версия от 00:19, 17 апреля 2012; Kasetkin (обсуждение | вклад) (Новая страница: «{{Определение |definition=<tex>TQBF</tex> расшивровывается как True Quantified Boolean Formula. Это язык верных бул...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
[math]TQBF[/math] расшивровывается как True Quantified Boolean Formula. Это язык верных булевых формул с квантилями. [math]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\}\}[/math]

Чтобы доказать, что [math]TQBF \in PS-complete[/math] необходимо показать что:

Лемма (1):
[math]TQBF \in PS[/math]
Лемма (2):
[math] \forall L \in PS \Rightarrow L \leq_p TQBF[/math]