Propositional Fragments for Knowledge Compilation and Quantified Boolean Formulae

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 20

Automated Reasoning

Several propositional fragments have been considered so far as target languages for knowledge compilation and used for improving computational tasks from major AI areas (like inference, diagnosis and planning); among them are the (quite influential) ordered binary decision diagrams, prime implicates, prime implicants, ``formulae'' in decomposable negation normal form. On the other hand, the validity problem QBF for Quantified Boolean Formulae (QBF) has been acknowledged for the past few years as an important issue for AI, and many solvers have been designed for this purpose. In this paper, the complexity of restrictions of {sc qbf} obtained by imposing the matrix of the input QBF to belong to such propositional fragments is identified. Both tractability and intractability results (PSPACE-completeness) are obtained.