TY - JOUR

T1 - Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions

AU - Shinohara, Ayumi

PY - 1995/1/9

Y1 - 1995/1/9

N2 - In the PAC-learning model, the Vapnik-Chervonenkis (VC) dimension plays the key role to estimate the polynomial-sample learnability of a class of {0, 1}-valued functions. For a class of {0, ..., N}-valued functions, the notion has been generalized in various ways. This paper investigates the complexity of computing VC-dimension and generalized dimensions: VC*-dimension, Ψ*-dimension, and ΨG-dimension. For each dimension, we consider a decision problem that is, for a given matrix representing a class F of functions and an integer K, to determine whether the dimension of F is greater than K or not. We prove that (1) both the VC*-dimension and ΨG-dimension problems are polynomial-time reducible to the satisfiability problem of length J with O(log2 J) variables, which include the original VC-dimension problem as a special case, (2) for every constant C, the satisfiability problem in conjunctive normal form with m clauses and C log2 m variables is polynomial-time reducible to the VC-dimension problem, while (3) Ψ*-dimension problem is NP-complete.

AB - In the PAC-learning model, the Vapnik-Chervonenkis (VC) dimension plays the key role to estimate the polynomial-sample learnability of a class of {0, 1}-valued functions. For a class of {0, ..., N}-valued functions, the notion has been generalized in various ways. This paper investigates the complexity of computing VC-dimension and generalized dimensions: VC*-dimension, Ψ*-dimension, and ΨG-dimension. For each dimension, we consider a decision problem that is, for a given matrix representing a class F of functions and an integer K, to determine whether the dimension of F is greater than K or not. We prove that (1) both the VC*-dimension and ΨG-dimension problems are polynomial-time reducible to the satisfiability problem of length J with O(log2 J) variables, which include the original VC-dimension problem as a special case, (2) for every constant C, the satisfiability problem in conjunctive normal form with m clauses and C log2 m variables is polynomial-time reducible to the VC-dimension problem, while (3) Ψ*-dimension problem is NP-complete.

UR - http://www.scopus.com/inward/record.url?scp=0029639925&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029639925&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(94)00164-E

DO - 10.1016/0304-3975(94)00164-E

M3 - Article

AN - SCOPUS:0029639925

SN - 0304-3975

VL - 137

SP - 129

EP - 144

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -