Satz TQBF ist nicht NL
Einfache Sprache
Def. Satz TQBF ist nicht NL
Beweisidee: Wir wissen nach Satz TQBF ist PSPACE-vollständig das TQBF in PSPACE ist. Nach folgender Überlegung sogar mit Log-Raum-Reduktion, weshalb dann
- “Though log space reducibility appears to be highly restrictive, it is adequate for most reductions in complexity theory because these are usually computa- tionally simple. For example, in Theorem 8.9 we showed that every PSPACE problem is polynomial time reducible to TQBF. The highly repetitive formu- las that these reductions produce may be computed using only log space, and therefore we may conclude that TQBF is PSPACE-complete with respect to log space reducibility. This conclusion is important because Corollary 9.6 shows that NL ( PSPACE. This separation and log space reducibility imply that TQBF 6 ∈ NL”