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. https://resolver.caltech.edu/CaltechAUTHORS:20200108-081611032
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:20200108-081611032
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.
| Item Type: | Book Section | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| Additional Information: | © 2008 Springer-Verlag Berlin Heidelberg. Supported by NSF CCF-0346991, CCF-0830787 and BSF 2004329. | |||||||||
| Funders: |
| |||||||||
| Subject Keywords: | Boolean Function; Full Version; Negative Instance; Logic Synthesis; Prime Implicants | |||||||||
| Series Name: | Lecture Notes in Computer Science | |||||||||
| Issue or Number: | 5369 | |||||||||
| DOI: | 10.1007/978-3-540-92182-0_52 | |||||||||
| Record Number: | CaltechAUTHORS:20200108-081611032 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20200108-081611032 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 100554 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 08 Jan 2020 19:59 | |||||||||
| Last Modified: | 16 Nov 2021 17:54 |
Repository Staff Only: item control page
