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 [math]\displaystyle{ w_C(c) }[/math]. The value [math]\displaystyle{ \max\{w_C(c):c\in C\} }[/math] is called the teaching dimension of C.