The problem is defined as follows:
Instance: A finite set $A$ of "possible diagnoses," a collection $C$ of subsets of $A$, representing binary "tests," and a positive integer $J≤|C|$.
Question: Is there a subcollection $C′⊆ C$ with $|C′|≤ J$ such that, for every pair $a_{i},a_{j}$ of possible diagnoses from $A$, there is some test $c∈C′$ for which $|{a_{i},a_{j}}|∩ c|=1$ (that is, a test $c$ that "distinguishes" between $a_{i}$ and $a_{j}$)?
And we know that MTC is $NP$-complete, it has been proved by reducing it to 3 Dimensional Matching problem in the Garey & Johnson's book.
Thanks.