Why is combinational ATPG efficiently solvable for practical VLSI circuits?

Empirical observation shows that practically encountered instances of combi national ATPG are efficiently solvable. However, it has been known for more than two decades that ATPG is an NP-complete problem (Ibarra and Sahni, IE EE Transactions on Computers, Vol. C-24, No. 3, pp. 242-249, March 1975). T his work is one of the first attempts to reconcile these seemingly disparat e results. We introduce the concept of cut-width of a circuit and character ize the complexity of ATPG in terms of this property. We introduce the clas s of log-bounded width circuits and prove that combinational ATPG is effici ently solvable on members of this class. The class of of log-bounded width circuits is shown to strictly subsume the class of k-bounded circuits intro duced by Fujiwara (International Symposium on Fault-Tolerant Computing, Jun e 1988, pp. 64-69). We provide empirical evidence which indicates that an i nterestingly large class of practical circuits is expected to have log-boun ded width, which ensures efficient solution of ATPG on them.