---
title: "Minimization for Generalized Boolean Formulas"
authors:
  - "Edith Hemaspaandra"
  - "Henning Schnoor"
doi: "10.5591/978-1-57735-516-8/IJCAI11-102"
url: "https://ijcai.org/proceedings/2011/102"
pdf: "https://ijcai.org/proceedings/2011/0102.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "566-570"
track: ""
keywords:
---

# Minimization for Generalized Boolean Formulas

Edith Hemaspaandra, Henning Schnoor

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 566-570. DOI: [10.5591/978-1-57735-516-8/IJCAI11-102](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.