The Vapnik-Chervonenkis dimension of a set system $(X,\mathcal S)$ with ground set $X$ is the maximum size of a set $X'\subseteq X$ such that for each subset $X'_i\subseteq X'$, there is a set $S_i\in\mathcal S$ with $S_i\cap X'=X'_i$.

The following decision problem is then natural:

Input: a set system $(X,\mathcal S)$ and an integer $k$.
Task: decide whether the VC dimension of $(X,\mathcal S)$ is at least $k$.

Since there are $2^{|X'|}$ subsets of $X'$, we have $|X'|\leq\log_2(|\mathcal S|)$, and hence VC DIMENSION can be solved in time $O\binom{|X|}{\log_2(|\mathcal S|)}$. For the hardness side, VC DIMENSION is LOGNP-hard (see here). However, I wonder whether something is known for the following specific case:

My question: what is the complexity of deciding whether a given set system $(X,\mathcal S)$ has VC dimension exactly $\log_2(|\mathcal S|)$?

  • 2
    $\begingroup$ Bla bla warning... Is there any reason to believe this is possible? Just think about generating a random set system, where every element is chosen with probability half to be in the set. It somehow seems you need to check all possible subsets, since all of them are going to look like decent candidates. $\endgroup$ Aug 16 '13 at 6:06

This doesn't answer the question, but it might be helpful. Mossel and Umans have made a detailed study of the complexity of approximating VC-dimension, when the set system is succinctly presented:

On the Complexity of Approximating the VC Dimension http://users.cms.caltech.edu/~umans/papers/MU01-final.ps

  • $\begingroup$ Thanks for the reference, but I'm rather interested in the case where the encoding is "classical" (i.e. not succint). $\endgroup$ Oct 31 '13 at 11:04

For the VC dimension to be exactly $\log_2(|\mathcal{S}|)$, $\mathcal{S}$ must be the powerset of some subset of $X$ of size $\log_2(|\mathcal{S}|)$, so you would need to check whether this is true, which takes, I'd say, time $O(|\mathcal{S}|)$.

  • $\begingroup$ How do you do this in time $O(|\mathcal S|)$? I think this checking has to go though all $\binom{|X|}{\log_2(|\mathcal S|)}$ such sets, giving a complexity of $O(|X|^{\log_2(|\mathcal S|)})$... $\endgroup$ Jul 16 '13 at 9:51
  • $\begingroup$ Scan $S$, find the elements of $S$| that have size 1. Label them from 1 to some $r$ arbitrarily. For the VC dimension to be exactly $\log_2(|\mathcal{S}|)$, $\mathcal{S}$ must contain all subsets of $\{1,\dotsc,r\}$. You can do another scan of $\mathcal{S}$ to check whether this is true. $\endgroup$
    – Matteo
    Jul 16 '13 at 13:57
  • $\begingroup$ @Matteo: I don't thing this works, sure you use the correct def of VC? $\endgroup$
    – domotorp
    Jul 16 '13 at 13:59
  • $\begingroup$ Florent is asking whether the VC is exactly $\log_2(\mathcal{S})$. The only way this can happen is if $\mathcal{S}$ is the powerset of some base set. You just have to check whether it is true or not. It shouldn't take more than scanning $\mathcal{S}$. $\endgroup$
    – Matteo
    Jul 16 '13 at 15:02
  • $\begingroup$ @Matteo, I don't think this works: indeed in a positive instance, for some set $X'\subseteq X$ the restriction of $\mathcal S$ to $X'$ must be the powerset of $X'$. But sets of $\mathcal S$ are allowed to contain elements of $X\setminus X'$. In particular, there might be no set of size one. $\endgroup$ Jul 16 '13 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.