Optimal Circuit Segmentation for Pseudo-Exhaustive Testing

摘要

This thesis explores a graph theory problem that arises from a circuit-testingproblem: Find an optimal segmentation for the pseudo-exhaustive testing of a combinational circuit. It translates the combinational circuit into a direct acyclic graph, and it proves that the resulting graph theory problem is in general NP-complete. Then it examines restricted versions of the problem-the number of segments might be limited, the fan-in or fan-out might be limited, or the graph might be otherwise constrained. It shows that although many restricted versions, too, are NP-complete, certain versions yield polynomial-time dynamic programming althorithms, and a reasonably well-defined boundary emerges between the two. Finally it considers approximating an optimal segmentation, and it shows in general that, unless P = NP, every polynomial-time algorithm for finding a segmentation will in the worst case be off from optimal by essentially an exponential factor. (Copyright (c) 1990 by Oren Patashnik.)