PS-полнота языка верных булевых формул с кванторами (TQBF)
Версия от 00:19, 17 апреля 2012; Kasetkin (обсуждение | вклад) (Новая страница: «{{Определение |definition=<tex>TQBF</tex> расшивровывается как True Quantified Boolean Formula. Это язык верных бул...»)
Определение: |
расшивровывается как True Quantified Boolean Formula. Это язык верных булевых формул с квантилями. |
Чтобы доказать, что
необходимо показать что:Лемма (1): |
Лемма (2): |