On the Computational Complexity of System Diagnosis
Fujiwara, Kinoshita · IEEE Transactions on Computers · 1978
In this paper we analyze the computational complexity of system diagnosis. We show that several problems for instantaneous and sequential fault diagnosis of systems are polynomially complete and that for single-loop systems these problems are solvable in polynomial time.