CaltechAUTHORS
  A Caltech Library Service

The Complexity of Boolean Formula Minimization

Buchfuhrer, David and Umans, Christopher (2008) The Complexity of Boolean Formula Minimization. In: Automata, Languages and Programming. Lecture Notes in Computer Science. No.5125. Springer , Berlin, pp. 24-35. ISBN 978-3-540-70574-1. https://resolver.caltech.edu/CaltechAUTHORS:20191112-131623581

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191112-131623581

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 Σ^P₂-complete and indeed appears as an open problem in Garey and Johnson [GJ79]. The depth-2 variant was only shown to be Σ^P₂-complete in 1998 [Uma98], 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₂-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₂-complete under Turing reductions.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/978-3-540-70575-8_3DOIArticle
https://resolver.caltech.edu/CaltechAUTHORS:20110422-100438828Related ItemJournal Article
https://rdcu.be/b3YkfPublisherFree ReadCube access
Additional Information:© 2008 Springer-Verlag Berlin Heidelberg. Supported by NSF CCF-0346991 and BSF 2004329. Supported by NSF CCF-0346991, BSF 2004329, a Sloan Research Fellowship, and an Okawa Foundation research grant.
Funders:
Funding AgencyGrant Number
NSFCCF-0346991
Binational Science Foundation (USA-Israel)2004329
Alfred P. Sloan FoundationUNSPECIFIED
Okawa FoundationUNSPECIFIED
Subject Keywords:Positive Instance; Boolean Formula; Negative Instance; Boolean Circuit; Equivalent Formula
Series Name:Lecture Notes in Computer Science
Issue or Number:5125
Record Number:CaltechAUTHORS:20191112-131623581
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20191112-131623581
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99813
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:12 Nov 2019 22:46
Last Modified:05 May 2020 20:18

Repository Staff Only: item control page