The Minimization Problem for Boolean Formulas

We investigate the computational complexity of the minimization problem for Boolean formulas. Depending on the definition, these problems are trivially in /spl Sigma//sub 2//sup P/ or II/sub 2//sup P/, and these are the best upper bounds known. The only previously known lower bounds are also trivial, and are coNP lower bounds at best, thus leaving quite a large gap between the upper and lower bounds. In this paper, we prove much better lower bounds: hardness for parallel access to NP for those cases in which coNP was the best previously known lower bound, and coNP-hardness for the case in which no lower bound was previously known.

Authors

• Edith Hemaspaandra
• Gerd Wechsung

Keywords

• Minimization
• Upper bound
• Polynomials
• Educational institutions
• Mathematics
• Computational complexity
• Robustness
• Boolean Formula
• Lower Bound
• Right-hand Side
• Independent Set
• Undirected
• New Variables
• Positive Integer
• Hand Side
• Reduction In Properties
• Lowest Common Ancestor
• Vertex Cover