|
Title:
|
THE COMPLEXITY OF CONSTRAINED QUANTIFIED FORMULAS |
|
Author(s):
|
Anja Remshagen |
|
ISBN:
|
978-972-8939-23-6 |
|
Editors:
|
António Palma dos Reis and Ajith P. Abraham |
|
Year:
|
2010 |
|
Edition:
|
Single |
|
Keywords:
|
Quantified Boolean formulas; Computational complexity. |
|
Type:
|
Full Paper |
|
First Page:
|
35 |
|
Last Page:
|
42 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
Quantified Boolean Formulas (QBFs) are a powerful representation that have been used to capture and solve a variety of problems in Artificial Intelligence. While most research has focused on quantified Boolean formulas in prenex normal form, we explore an alternative representation of quantified Boolean formulas, called constrained quantified formulas that allows for a more direct representation of many applications. We show that the complexity of two subclasses of constrained quantified Boolean formulas, the Horn and 2CNF case, is reduced by one, respectively, two levels in the polynomial hierarchy. In contrast, quantified Boolean formulas in prenex normal form collapse to the first level of the polynomial hierarchy in case of Horn or 2CNF formulas. |
|
|
|
|
|
|
