Backdoors for Quantified Boolean FormulasResearch Paper
A quantified Boolean formula (QBF) quantifies every variable of a Boolean matrix by a prefix , . Deciding its truth is the canonical PSPACE-complete problem. It is the natural target for problems in verification, planning and non-monotonic reasoning that lie above NP.