On the complexity of generating optimal test sequences
Sylvia C. Boyd, Hasan Ural · IEEE Transactions on Software Engineering · 1991
The authors investigate whether maximal overlapping of protocol test subsequences can be achieved in polynomial time. They review the concepts related to FSM (finite state machine)-based test sequence generation and then define the optimal test sequence generation (OTSG) problem. It is proved that the OTSG problem is NP-complete. Therefore an efficient solution to the problem should not be expected in the general case.>