The problem of generating a minimum test set for pair-wise testing is NP-complete

The problem of generating a minimum test set for pair-wise testing is NP-complete.

References:

• An Improved Test Generation Algorithm for Pair-Wise Testing, by Soumen Maity, Amiya Nayak, Marzia Zaman, Nita Bansal, and Alka Srivastava

• Lei, Y and Tai, K. C., In-Parameter-Order: A Test Generating Strategy for Pairwise Testing, IEEE Trans. on Software Engineering, 2002, 28 (1), 1-3.