On the Complexity of Estimating the Size of a Test Set
- 1 August 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (8), 750-753
- https://doi.org/10.1109/tc.1984.5009364
Abstract
Most NP-completeness results for test generation problems involve a reduction to the redundancy problem, which explicitly encodes the satisfiability problem. In this correspondence we investigate the complexity of a more modest problem-that of estimating the size of a test set under the constraint that the circuit is irredundant. We show that even this constrained problem is NP-hard in the strong sense.This publication has 6 references indexed in Scilit:
- The Complexity of Fault Detection Problems for Combinational Logic CircuitsIEEE Transactions on Computers, 1982
- On Closedness and Test Complexity of Logic CircuitsIEEE Transactions on Computers, 1981
- Polynomially Complete Fault Detection ProblemsIEEE Transactions on Computers, 1975
- Test Point Placement to Simplify Fault DetectionIEEE Transactions on Computers, 1974
- Universal Test Sets for Logic NetworksIEEE Transactions on Computers, 1973
- Derivation of Minimum Test Sets for Unate Logical CircuitsIEEE Transactions on Computers, 1971