A Caltech Library Service

The Complexity of SPP Formula Minimization

Buchfuhrer, David (2008) The Complexity of SPP Formula Minimization. In: Algorithms and Computation. Lecture Notes in Computer Science. No.5369. Springer , Berlin, pp. 580-591. ISBN 978-3-540-92181-3.

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

Use this Persistent URL to link to this item:


Circuit minimization is a useful procedure in the field of logic synthesis. Recently, it was proven that the minimization of ( ∨ , ∧ ,¬) formulae is hard for the second level of the polynomial hierarchy [BU08]. The complexity of minimizing more specialized formula models was left open, however. One model used in logic synthesis is 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 was known about the complexity of SPP minimization. Here, we show that SPP minimization is complete for the second level of the Polynomial Hierarchy under Turing reductions.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access
Additional Information:© 2008 Springer-Verlag Berlin Heidelberg. Supported by NSF CCF-0346991, CCF-0830787 and BSF 2004329.
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2004329
Subject Keywords:Boolean Function; Full Version; Negative Instance; Logic Synthesis; Prime Implicants
Series Name:Lecture Notes in Computer Science
Issue or Number:5369
Record Number:CaltechAUTHORS:20200108-081611032
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100554
Deposited By: Tony Diaz
Deposited On:08 Jan 2020 19:59
Last Modified:16 Nov 2021 17:54

Repository Staff Only: item control page