Return to Revisions

Although a proof of NP-completeness is already provided, it might be worth pointing out that this problem is equivalent to a known NP-complete problem called the minimum test set problem ([SP6] in Garey and Johnson, also called the minimum test collection problem): just exchange the role of the sets and the role of the positions.