Published December 10, 2008
| public
Book Section - Chapter
The Complexity of SPP Formula Minimization
- Creators
- Buchfuhrer, David
Abstract
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.
Additional Information
© 2008 Springer-Verlag Berlin Heidelberg. Supported by NSF CCF-0346991, CCF-0830787 and BSF 2004329.Additional details
- Eprint ID
- 100554
- DOI
- 10.1007/978-3-540-92182-0_52
- Resolver ID
- CaltechAUTHORS:20200108-081611032
- CCF-0346991
- NSF
- CCF-0830787
- NSF
- 2004329
- Binational Science Foundation (USA-Israel)
- Created
-
2020-01-08Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
- Series Name
- Lecture Notes in Computer Science
- Series Volume or Issue Number
- 5369