A Caltech Library Service

The complexity of Boolean formula minimization

Buchfuhrer, David and Umans, Christopher (2011) The complexity of Boolean formula minimization. Journal of Computer and System Sciences, 77 (1). pp. 142-153. ISSN 0022-0000. doi:10.1016/j.jcss.2010.06.011.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemBook Chapter
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.
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2004329
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:Formula minimization; Computational complexity; Logic synthesis; Polynomial-Time Hierarchy; Turing reduction
Issue or Number:1
Record Number:CaltechAUTHORS:20110422-100438828
Persistent URL:
Official Citation:David Buchfuhrer, Christopher Umans, The complexity of Boolean formula minimization, Journal of Computer and System Sciences, Volume 77, Issue 1, Celebrating Karp's Kyoto Prize, January 2011, Pages 142-153, ISSN 0022-0000, DOI: 10.1016/j.jcss.2010.06.011. (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:23422
Deposited By: Tony Diaz
Deposited On:22 Apr 2011 18:00
Last Modified:09 Nov 2021 16:14

Repository Staff Only: item control page