Minimization for Generalized Boolean Formulas

Hemaspaandra, Edith; Schnoor, Henning

doi:10.5591/978-1-57735-516-8/IJCAI11-102

Minimization for Generalized Boolean Formulas

Edith Hemaspaandra, Henning Schnoor

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 566-570.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-102

Abstract

The minimization problem for propositional formulas is an important optimization problem in the second level of the polynomial hierarchy. In general, the problem is Sigma-2-complete under Turing reductions, but restricted versions are tractable. We study the complexity of minimization for formulas in two established frameworks for restricted propositional logic: The Post framework allowing arbitrarily nested formulas over a set of Boolean connectors, and the constraint setting, allowing generalizations of CNF formulas. In the Post case, we obtain a dichotomy result: Minimization is solvable in polynomial time or coNP-hard. This result also applies to Boolean circuits. For CNF formulas, we obtain new minimization algorithms for a large class of formulas, and give strong evidence that we have covered all polynomial-time cases.

Edith Hemaspaandra, and Henning Schnoor. 2011. Minimization for Generalized Boolean Formulas. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 566–570. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-102

@inproceedings{ijcai2011p102,
  title     = {Minimization for Generalized Boolean Formulas},
  author    = {Hemaspaandra, Edith and Schnoor, Henning},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {566--570},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-102},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-102},
}

TY  - CPAPER
TI  - Minimization for Generalized Boolean Formulas
AU  - Hemaspaandra, Edith
AU  - Schnoor, Henning
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 566
EP  - 570
DO  - 10.5591/978-1-57735-516-8/IJCAI11-102
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-102
ER  -