Polynomially Complete Fault Detection Problems
- 1 March 1975
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-24 (3) , 242-249
- https://doi.org/10.1109/t-c.1975.224205
Abstract
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.Keywords
This publication has 7 references indexed in Scilit:
- Complete register allocation problemsPublished by Association for Computing Machinery (ACM) ,1973
- Polynomial complete scheduling problemsPublished by Association for Computing Machinery (ACM) ,1973
- Easily Testable Realizations ror Logic FunctionsIEEE Transactions on Computers, 1972
- Some related problems from network flows, game theory and integer programmingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1972
- Multiple faults in Reed-Muller canonic networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1972
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971