On the nonenumerative path delay fault simulation problem. - Kagaris, D.
The problem of determining the exact number of path delay faults that a given test set detects in a combinational circuit is shown to be intractable. This result further strengthens the importance of several recently proposed pessimistic heuristics as well as exact exponential algorithms for this nonenumerative problem. A polynomial time pessimistic algorithm which returns higher coverage than algorithms with the same order of complexity and at the same time compacts the test set is also presented
Keywords: NP-hardness.; Automatic test pattern generation; Combinational circuit; Exact exponential algorithms; Fault simulation; Nonenumerative problem; Path delay faults; Pessimistic heuristics; Polynomial time pessimistic algorithm