Complexity Comparisons in Logic Testing

Abstract

The paper is concerned with analyzing and comparing two exact algorithms from the viewpoint of computational complexity. Both serve for calculating fault-detection tests of digital circuits. The first one is the so-called composite justification, and the second is the D-algorithm. The analysis will be performed on combinational logic networks at the gate level. Here single and multiple stuck-at logic faults will be considered. As a result, it is pointed out that the composite justification requires significantly less computational step than the D-algorithm and its modifications. From this fact it has been conjectured that possibly no other algorithm is available in this field with fewer computational steps. If the claim holds, then it follows directly that the test-calculation problem is of exponential time, and so are all the other NP-complete problems. It may also be expected that the minimal complexity of composite justification applies to any modeling level (either low or high) of digital circuits, just like the exponential-time
solution.