Witness set

In computational learning theory, let "C" be a concept class over a domain "X" and "c" be a concept in "C". A subset "S" of "X" is a witness set for "c" in "C" if "c"("S") verifies "c" (i.e., "c" is the only consistent concept with respect to "c"("S")). The minimum size of a witness set for "c" is called the "witness size" or "specification number" and is denoted by $w\_C(c)$. The value $max\{w\_C(c):cin\; C\}$ is called the teaching dimension of "C".