Minimization for Generalized Boolean Formulas

Details Minimization for Generalized Boolean Formulas Minimization for Generalized Boolean Formulas

2011-04-12

arxiv.org/abs/1104.2312v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Minimization for Generalized Boolean Formulas does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimization for Generalized Boolean Formulas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimization for Generalized Boolean Formulas will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-731155