ON POLYNOMIAL-TIME TESTABLE COMBINATIONAL-CIRCUITS

The problems of identifying several nontrivial classes of Polynomial-T ime Testable (PTT) circuits are shown to be NP-complete or harder. Fir st, PTT classes obtained by using circuit decompositions proposed by F ujiwara and Chakradhar et al. are considered. Another type of decompos itions, based on fanout-reconvergent (f-r) pairs, which also lead to P TT classes are proposed. The problems of obtaining these decomposition s, and also some structurally similar general graph decompositions, ar e shown to be NP-complete or harder. Then, the problems of recognizing PTT classes formed by the Boolean formulae belonging to the weakly po sitive, weakly negative, bijunctive and affine classes (proposed by Sc haefer) are shown to be NP-complete.