Deciding the Vapnik–Červonenkis Dimension is∑p3-complete

摘要

N. Linialet al.raised the question of how difficult the computation of the Vapnik–Červonenkis dimension of a concept class over a finite universe is. C. Papadimitriou and M. 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 VC DIMENSION problem. We establish that VC DIMENSION is∑p3-complete, thereby giving a rare natural example of a∑p3-complete problem.