Zeige, dass ERREICHBARKEIT NL-vollständig ist.
Zeige, dass 2SAT NL-vollständig ist.
Zeige, dass QSAT PSPACE-vollständig ist.
Dabei ist QSAT (Quantified Satisfiability) folgendes Problem: Gegeben eine Boolsche Formel PHI in konjunktiver Normalform mit Boolschen Variablen x_1,...,x_n. Stimmt es, dass es einen Wahrheitswert für x_1 gibt, sodass für beide möglichen Wahrheitswerte von x_2, es einen Wahrheitswert für x_3 gibt, sodass für beide möglichen Wahrheitswerte von x_4, usw bis x_n (wobei der n. Quantor ein Allquantor ist, wenn n gerade ist, sonst ein Existenzquantor), sodass PHI erfüllt ist?
Hinweis: QSAT ist auch unter dem Namen QBF (Quantified Boolean Formula) bekannt. Beweis ähnlich wie bei Cook's Beweis der NP-Vollständigkeit von SAT unter Verwendung des Tricks in Savitchs Theorem um Platz zu sparen, damit die enstehenden Formeln nicht zu lange werden.