On the nonenumerative path delay fault simulation problem

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