Example of Minimum Test Collection Problem
The formal definition of the problem from Garey and Johnson is


  Minimum Test Collection
  
  Instance: A finite set $A$ of "possible diagnoses," a collection&nbsp;$C$ of subsets of&nbsp;$A$, representing binary "tests," and a positive integer $J\leq |C|$.
  
  Question: Is there a subcollection $C'\subseteq C$ with $|C'|\leq J$ such that, for every pair $a_i,a_j$ of possible diagnoses from&nbsp;$A$, there is some test $c\in C'$ for which $|\{a_i,a_j\}|\cap c|=1$ (that is, a test&nbsp;$c$ that "distinguishes" between $a_i$ and&nbsp;$a_j$)?


Think of $A$ as a set of diseases, and each element of&nbsp;$C$ is a set of all the diseases in&nbsp;$A$ that have some particular symptom.  You can use these sets to figure out what disease a person has. For example (not necessarily medically accurate), suppose our diseases are
$$A = \{\mathrm{flu}, \mathrm{measles}, \mathrm{ebola}\}$$
and our tests are
$$C = \{\mathrm{cough}, \mathrm{rash}, \mathrm{bleeding}\}\,,$$
where
\begin{align*}
\mathrm{cough} &amp;= \{\mathrm{flu}, \mathrm{ebola}\}\\
\mathrm{rash}  &amp;= \{\mathrm{measles}, \mathrm{ebola}\}\\
\mathrm{bleeding} &amp;= \{\mathrm{ebola}\}\,.
\end{align*}

A doctor might try to diagnose a patient by checking whether they have a cough and/or a rash and whether they're bleeding. Minimum Test Collection asks if we can do any better than that, since tests might be expensive to carry out.

In this case, we can.  It's enough to check whether the patient is coughing and whether they're bleeding. If they're bleeding, we know they have ebola. If they're not bleeding, but they are coughing, they have the flu; if they're neither bleeding nor coughing, they must have the measles.  (Note we're assuming as part of our test procedure that these are the only three diseases in the world, and that people only go to the doctor if they have at least one symptom.)