Polynomially Complete Fault Detection Problems
Óscar H. Ibarra, Sartaj K. Sahni · IEEE Transactions on Computers · 1975
We look at several variations of the single fault detection problem for combinational logic circuits and show that deciding whether single faults are detectable by input-output (I/O) experiments is polynomially complete, i.e., there is a polynomial time algorithm to decide if these single faults are detectable if and only if there is a polynomial time algorithm for problems such as the traveling salesman problem, knapsack problem, etc.