The computational complexity of fault detection problems and various controllability and observability problems for combinational logic circuits are analyzed. It is shown that the fault detection problem is still NP-complete for monotone circuits limited in fanout, i.e. when the number of signal lines which can out from a signal line is limited to two. It is also shown that the observability problem for unate circuits is NP-complete, but that the controllability problem for unate circuits can be solved in time complexity O(m), where m is the number of lines in a circuit. Two classes of circuits, called k-binate-bounded circuits and k-bounded circuits, are then introduced. For k-binate-bounded circuits the controllability problem is solvable in polynomial time, and for k-bounded circuits the fault detection problem is solvable in polynomial time, when k >
['Hideo Fujiwara']
Computational complexity of controllability/observability problems for combinational circuits