The most important problem this paper deals with seems to be the “observability problem.” Let C be a combinational circuit, and let A and B be particular input and output lines, respectively. Is there an assignment to each of the input lines other than A so that any changes in the value of A would be observed at B? It was shown by Ibarra and Sahni [1] that the general case of the observability problem as well as the general cases of a few other fault-detection problems are NP-complete. Fujiwara and Toida showed [2] that these problems are still NP-complete when the circuits are monotone, which roughly means that they have no “negated” gates such as NOT, NAND, NOR, or even XOR.

The main thrust of the first half of this paper seems to be to understand what “causes” the NP-hardness of fault detection problems. More specifically, the author imposes more and more restrictions on the problems until they have polynomial solutions. Such a study gives a rough understanding of the “cause” of NP-hardness in the sense that the study shows what it takes to “make the NP-hardness disappear.” Fujiwara has found, for example, that if we limit (to a constant) the total number of points with a fanout of greater than 1 in the circuit, then the observability problem ceases to be NP-hard.

The second half of the paper gives polynomial-time algorithms for fault detection problems in certain special classes of combinational circuits that include some practical circuits such as ripple adders, decoders, and cellular arrays.

The paper is an example of the application of clever theoretical principles to practical problems outside of classical computer science, and in that sense it is interesting. As theoretical computer science matures, a tendency is developing among theoretical computer scientists to apply the powerful techniques of theory to solve problems outside of classical computer science. I believe that this trend is healthy because it may help to tie theory to the rest of world knowledge, and thus may help to keep theory alive and well. The paper under review, however, deals with issues that seem a bit too detailed for circuit design engineers to care about. While it is quite interesting to know that the general cases of the fault detection problems are NP-hard, the special cases considered in the paper may be somewhat too specialized unless a special context exists in which these cases are important.

Fujiwara’s paper is not as well written as one would normally expect a paper in theory to be. The main problem is a lack of precision in the definition of terms. The results seem to be mathematically correct, however, and they can be followed once the reader has understood the intended meanings of the terms used in the paper.