<テクニカルレポート>
Complexity of Computing Vapnik-Chervonenkis Dimension

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 The Vapnik-Chervonenkis (VC) dimension is known to be the crucial measure of the polynomial-sample learnability in the PAC-learning model. This paper investigates the complexity of computing VC-dimens...ion of a concept class over a finite learning domain. We consider a decision problem called the discrete VC-dimension problem which is, for a given matrix representing a concept class F and an integer K, to determine whether the VC-dimension of F is greater than K or not. We prove that (1) the discrete VC-dimension problem is polynomial-time reducible to the satisfiability problem of length J with $ O left(log^2 J\right) $ variables, and (2) for every constant C, the satisfiability problem in conjunctive normal form with m clauses and $ C log^2 m $ variables is polynomial-time reducible to the discrete VC-dimension problem. These results can be interpreted, in some sense, that the problem is "complete" for the class of $ n^oleft(log n\right) $ time computable sets.続きを見る

本文情報を非表示

rifis-tr-69 pdf 636 KB 85  

詳細

レコードID
査読有無
関連情報
注記
タイプ
登録日 2009.04.22
更新日 2017.01.20