On Polynomial-Time Testable Combinational Circuits

Nageswara S.V. Rao

doi:10.1109/12.324562

On Polynomial-Time Testable Combinational Circuits

Nageswara S.V. Rao

Autonomous and Complex Systems

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

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	https://doi.org/10.1109/12.324562
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.

Funders	Funder number
Office of Basic Energy Sciences
National Science Foundation	IRI-9108610
U.S. Department of Energy	DE-AC05-840R21400
Old Dominion University

Keywords

Test generation
and NP-completeness
combinational circuits
polynomial-time testability

Access to Document

10.1109/12.324562

Cite this

@article{f796bd8c90c2491ab8aa0d4800a562a0,

title = "On Polynomial-Time Testable Combinational Circuits",

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.",

keywords = "Test generation, and NP-completeness, combinational circuits, polynomial-time testability",

author = "Rao, {Nageswara S.V.}",

year = "1994",

month = nov,

doi = "10.1109/12.324562",

language = "English",

volume = "43",

pages = "1298--1308",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "Institute of Electrical and Electronics Engineers",

number = "11",

}

TY - JOUR

T1 - On Polynomial-Time Testable Combinational Circuits

AU - Rao, Nageswara S.V.

PY - 1994/11

Y1 - 1994/11

N2 - 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.

AB - 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.

KW - Test generation

KW - and NP-completeness

KW - combinational circuits

KW - polynomial-time testability

UR - http://www.scopus.com/inward/record.url?scp=0028532746&partnerID=8YFLogxK

U2 - 10.1109/12.324562

DO - 10.1109/12.324562

M3 - Article

AN - SCOPUS:0028532746

SN - 0018-9340

VL - 43

SP - 1298

EP - 1308

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 11

ER -

On Polynomial-Time Testable Combinational Circuits

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this