Bondy's theorem

From Wikipedia, the free encyclopedia

Bondy's theorem is a theorem in computational learning theory that appear in a 1972 article by Adrian Bondy. The theorem is as follows:

Let C be a concept class over a finite domain X. Then there exists a subset S of X with the size at most |C| − 1 such that S is a witness set for every concept in C.

This implies that every finite concept class C has its teaching dimension bounded by |C| − 1.