Subclasses of Quantified Boolean Formulas

Abstract Using the results of a former paper of two of the authors [KaKB 90], for certain subclasses of quantified Boolean formulas it is shown, that the evaluation problems for these classes are coNP-complete. These subclasses can be seen as extensions of Horn and 2-CNF formulas. Further it is shown that the evaluation problem for quantified CNF formulas remains PSPACE-complete, even if at most one universal variable is allowed in each clause.

Authors

• Andreas Flögel
• Marek Karpinski
• Hans Kleine Büning

Keywords

No keywords are indexed for this paper.