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

✍ Scribed by Marcus Schaefer

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 160 KB
• Volume: 58
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1998.1602

✦ Synopsis

N. Linial et al. raised the question of how difficult the computation of the Vapnik C 8 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 7 p 3 -complete, thereby giving a rare natural example of a 7 p 3 -complete problem.