## ＜テクニカルレポート＞Complexity of Computing Vapnik-Chervonenkis Dimension

作成者 作成者姓名 Shinohara, Ayumi 篠原, 歩 所属機関 所属機関名 Research Institute of Fundamental Information Science Kyushu University 九州大学理学部附属基礎情報学研究施設 英語 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 1993-04-29 RIFIS Technical Report 69 accepted open access 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 3172 査読無 RIFIS Technical Report || 69 || p1-10 http://www.i.kyushu-u.ac.jp/research/report.html Lecture Notes in Artificial Intelligence 744, 279-287, 1993 テクニカルレポート 2009.04.22 2017.01.20