Propositional fragments for knowledge compilation and quantified boolean formulae

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 in-ference, diagnosis and planning); among them are the (quite influential) ordered binary decision diagrams, prime impli-cates, prime implicants, “formulae ” in decomposable nega-tion normal form. On the other hand, the validity problem QBF for Quantified Boolean Formulae (QBF) has been ac-knowledged 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 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