Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1990 Copyright 1990 University of Bonn, Department of Computer Science, Abt. V
8559

Subclasses of Quantified Boolean Formulas
Andreas Floegel, Marek Karpinski, Hans Kleine-Buening
[Download PostScript] [Download PDF]

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

Last Change: 08/18/99 at 13:00:38
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V