Optimal circuit segmentation for pseudo-exhaustive testing
Oren Patashnik · 1990
This thesis explores a graph theory problem that arises from a circuit-testing problem: Find an optimal segmentation for the pseudo-exhaustive testing of a combinational circuit. It translates the combinational circuit into a directed 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 algorithms, 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.