Deciding The Vapnik-Chervonenkis Dimension Is Sigma_3-Complete
Marcus Schaefer · Conference on Computational Complexity · 1996
Linial, Mansour and Rivest in 1988 raised the question of how difficult the computation of the Vapnik-Chervonenkis dimension of a concept class over a finite universe is. Papadimitriou and Yannakakis 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 VAPNIK-CHERVONENKIS problem. We establish that VAPNIK-CHERVONENKIS is complete for sigma_3, thereby giving a rare natural example for a complete problem at that level.