article · 2002
Deciding the Vapnik-Cervonenkis dimension is Σ/sub 3//sup p/-complete
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. P...
0 citationsDOI: https://doi.org/10.1109/ccc.1996.507670