Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2011 | public
Journal Article Open

The complexity of Boolean formula minimization


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 Σ^P_2-complete and indeed appears as an open problem in Garey and Johnson (1979) [5]. The depth-2 variant was only shown to be Σ^P_2-complete in 1998 (Umans (1998) [13], Umans (2001) [15]) 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 Σ^P_2-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 Σ^P_2-complete under Turing reductions.

Additional Information

© 2010 Elsevier Inc. Received 30 May 2009; revised 3 January 2010. Available online 11 June 2010. Supported by NSF CCF-0830787, and BSF 2004329. Supported by NSF CCF-0830787 and a Sloan Research Fellowship. We thank Edith Hemaspaandra for helpful comments on a draft of this paper, and the anonymous reviewers for their comments and corrections.

Attached Files

Submitted - E44467B7d01.pdf


Files (227.0 kB)
Name Size Download all
227.0 kB Preview Download

Additional details

August 22, 2023
August 22, 2023