Minimization for Generalized Boolean Formulas

Edith Hemaspaandra, Henning SchnoorIJCAI 2011 · DOI

TL;DR

This paper tackles the problem of finding the smallest equivalent Boolean formula for a given formula. The authors provide a complete complexity classification for this problem in the "Post framework" and make significant progress in the "constraint framework," identifying tractable cases and proving hardness for others. This work clarifies when minimizing Boolean formulas is computationally feasible and when it becomes a hard problem.

What Problem Does This Paper Address?

The core problem is Boolean formula minimization: given a Boolean formula, find an equivalent formula that is as small as possible. "Smallness" can be defined in various ways, such as the number of literals or function symbols. This problem is fundamental in areas like circuit design and knowledge representation, where compact representations are crucial. While the general problem is known to be hard (coNP-hard), understanding its complexity in restricted settings is vital for practical applications. This paper focuses on two such settings:

  1. The Post framework: This framework generalizes Boolean logic by allowing arbitrary sets of Boolean functions as connectors, offering more expressive power and potentially more succinct representations than standard AND, OR, and NOT.
  2. The constraint framework: This framework restricts formulas to specific clause types (like Horn clauses or XOR clauses) defined by a "constraint language."

The paper aims to provide a comprehensive understanding of the minimization problem's complexity within these frameworks, identifying which restrictions lead to efficient solutions and which remain computationally challenging.

Methods

The paper employs a combination of theoretical computer science techniques, including:

  • Complexity Analysis: The authors rigorously analyze the computational complexity of minimization problems, classifying them as polynomial-time solvable or NP-hard/coNP-hard.
  • Reductions: They use reductions from known hard problems (like satisfiability and equivalence) to prove hardness results for minimization.
  • Algorithmic Construction: For tractable cases, they develop polynomial-time algorithms that not only determine if a smaller equivalent formula exists but also construct it.
  • Framework-Specific Techniques:
    • In the Post framework, they leverage the duality of Boolean functions and analyze the properties of different sets of connectors to establish a dichotomy result (either polynomial-time solvable or coNP-hard).
  • In the constraint framework, they introduce and utilize the concept of irreducible relations and Schaefer languages. They develop algorithms for specific classes of irreducible constraint languages (affine, bijunctive, IHSB+/IHSB-) and prove hardness for others.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on complexity analysis rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Dichotomy in the Post Framework: The paper establishes a clean "dichotomy" for the Post framework: for any set of Boolean functions, minimization is either solvable in polynomial time or coNP-hard. This is a strong theoretical result, simplifying the landscape of complexity for this setting.
  • Irreducibility is Key for Tractability: In the constraint framework, the concept of "irreducible relations" (relations that cannot be decomposed into simpler independent conditions) is crucial for achieving polynomial-time solvability. Languages composed of irreducible relations are more amenable to efficient minimization.
  • Minimization is Different: The authors highlight that minimization behaves differently from other constraint satisfaction problems (like satisfiability or equivalence). Standard algebraic tools used for those problems don't directly apply to minimization, especially in the constraint setting.
  • The Power of "Building Blocks": In the constraint framework, the hardness often arises not from the fundamental task of finding a minimal representation but from the complexity of using the allowed "building blocks" (relations) efficiently.
  • A Complete Classification for Schaefer Languages: The paper provides a complete classification of minimization complexity for irreducible constraint languages that are "Schaefer" (a broad class including affine, bijunctive, Horn, and dual Horn).

Key Results

  • Post Framework: A complete classification is achieved: minimization is polynomial-time solvable or coNP-hard.
  • Constraint Framework (Schaefer Languages):
    • Polynomial-time solvability is established for irreducible constraint languages that are affine, bijunctive, IHSB+, or IHSB-.
  • For Horn or dual Horn languages (that are not IHSB-), minimization is NP-complete.
  • For non-Schaefer languages, minimization is coNP-hard.
  • Hardness for Non-Irreducible Languages: The paper demonstrates that non-irreducibility can lead to NP-hardness even when the language's expressive power is limited (e.g., Example 3.2).

Limitations and Future Work

  • Open Questions in coNP-hard Cases: The paper acknowledges that the exact complexity of all coNP-hard cases in the constraint framework remains open, though it's conjectured that most are NP-hard.
  • E-completeness: It would be interesting to determine if any of these minimization problems are E-complete (a higher complexity class).
  • Influence of Non-Irreducibility: A deeper understanding of how non-irreducibility specifically impacts complexity is suggested as a future research direction.
  • General CNF Formulas: While the paper focuses on restricted settings, the complexity of minimization for general CNF formulas is mentioned as a related, but distinct, problem.

Summary updated

BibTeX
@inproceedings{hemaspaandra2011minimization,
  author = {Edith Hemaspaandra and Henning Schnoor},
  title = {{Minimization for Generalized Boolean Formulas}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.5591/978-1-57735-516-8/ijcai11-102},
}
Figure