On the complexity of non-unique probe selection

We investigate the computational complexity of some basic problems regarding non-unique probe selection using separable matrices. In particular, we prove that the minimal -separable matrix problem is -complete, and the -separable submatrix with reserved rows problem, which is a generalization of the decision version of the minimum -separable submatrix problem, is -complete.