|
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 |