Deciding the Vapnik-Cervonenkis dimension is Σ/sub 3//sup p/-complete
Marcus Schäfer · 2002
Linial et al. (1988) raised the question of how difficult the computation of the Vapnik-Cervonenkis dimension of a concept class over a finite universe is. Papadimitriou and Yannakakis (1993) obtained a first answer using matrix representations of concept classes. However, this approach does not capture classes having exponential size, like monomials, which are encountered in learning theory. We choose a more natural representation, which leads us to redefine the VC DIMENSION problem. We establish that VC DIMENSION is /spl Sigma//sub 3//sup p/-complete, thereby giving a rare natural example of a /spl Sigma//sub 3//sup p/-complete problem.