The Complexity of Formula Minimization

Citation

Buchfuhrer, David Isaac (2008) The Complexity of Formula Minimization. Master's thesis, California Institute of Technology. doi:10.7907/9T9K-4394. https://resolver.caltech.edu/CaltechETD:etd-05292008-183055

Abstract

The Minimum Equivalent Expression problem is a natural optimization problem in the second level of the Polynomial-Time Hierarchy. It has long been conjectured to be Σ₂-complete and indeed appears as an open problem in Garey and Johnson. The depth-2 variant was only shown to be Σ₂-complete in 1998, and even resolving the complexity of the depth-3 version has been mentioned as a challenging open problem. We prove that the depth-k version is Σ₂-complete under Turing reductions for all k >= 3. We also settle the complexity of the original, unbounded depth Minimum Equivalent Expression problem, by showing that it too is Σ₂-complete under Turing reductions.

We also consider a three-level model in which the third level is composed of parity gates, called SPPs. SPPs allow for small representations of Boolean functions and have efficient heuristics for minimization. However, little has been known about the complexity of SPP minimization. Here, we show that SPP minimization is Σ₂-complete under Turing reductions.

Thesis Files