Deciding the Vapnik-Červonenkis Dimension in ∑p3-Complete
Deciding the Vapnik-Červonenkis Dimension in ∑p3-Complete
复制标题
确定 Σp3-Complete 中的 Vapnik-Červonenkis 维数
DOI：
10.1006/jcss.1998.1602
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
M. Schaefer
中科院分区：
文献类型：
--
作者：
M. Schaefer
N. linialet al。提出了一个问题，即在有限宇宙上概念类别的Vapnik ervonenkis维度的计算有多困难。 C. Papadimitriou和M. Yannakakis使用概念类的矩阵表示获得了第一个答案。但是，这种方法并未捕获具有指数尺寸的类，例如单元，这些课程在学习理论中遇到。我们选择更自然的表示，这使我们重新定义了VC维度问题。我们确定VC尺寸为“ P3完整”，从而给出了一个罕见的自然示例。
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.