A Caltech Library Service

The Complexity of Formula Minimization


Buchfuhrer, David Isaac (2008) The Complexity of Formula Minimization. Master's thesis, California Institute of Technology. doi:10.7907/9T9K-4394.


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 Σ2-complete and indeed appears as an open problem in Garey and Johnson. The depth-2 variant was only shown to be Σ2-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 Σ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 Σ2-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 Σ2-complete under Turing reductions.

Item Type:Thesis (Master's thesis)
Subject Keywords:MEE; pseudoproduct
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Unknown, Unknown
Thesis Committee:
  • Unknown, Unknown
Defense Date:30 May 2008
Additional Information:An extended abstract version of the material presented in Chapter 2 appeared in ICALP in 2008 [BU08]: ICALP 2008, 35th International Colloquium on Automata, Languages and Programming (July 6 - 13, 2008, Reykjavik, Iceland).
Record Number:CaltechETD:etd-05292008-183055
Persistent URL:
Related URLs:
URLURL TypeDescription ItemPaper presented at ICALP 2008
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2264
Deposited By: Imported from ETD-db
Deposited On:02 Jun 2008
Last Modified:26 Nov 2019 21:33

Thesis Files

PDF (formula_minimization.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page