Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1990 Copyright 1990 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope