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.