Abstract
The problems of identifying several nontrivial classes of Polynomial-Time Testable (PTT) circuits are shown to be NP-complete or harder. First, PTT classes obtained by using circuit decompositions proposed by Fujiwara and Chakradhar et al. are considered. Another type of decompositions, based on fanout-reconvergent (f-τ) pairs, which also lead to PTT classes are proposed. The problems of obtaining these decompositions, and also some structurally similar general graph decompositions, are shown to be NP-complete or harder. Then, the problems of recognizing PTT classes formed by the Boolean formulae belonging to the weakly positive, weakly negative, bijunctive and affine classes (proposed by Schaefer) are shown to be NP-complete.
| Original language | English |
|---|---|
| Pages (from-to) | 1298-1308 |
| Number of pages | 11 |
| Journal | IEEE Transactions on Computers |
| Volume | 43 |
| Issue number | 11 |
| DOIs | |
| State | Published - Nov 1994 |
Funding
Manuscript received August 6, 1992; revised August 13, 1993. This work was supported by the Engineering Research Program of the Office of Basic Energy Sciences, of the US. Department of Energy, under Contract DE-AC05-840R21400 with Martin Marietta Energy Systems, Inc., Old Dominion University Summer Faculty Award for 1991, and also by National Science Foundation under Grant IRI-9108610.
Keywords
- Test generation
- and NP-completeness
- combinational circuits
- polynomial-time testability