7
$\begingroup$

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:

VC DIMENSION
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|)$?

Improve this question
$\endgroup$
1
  • 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$
    – Sariel Har-Peled
    Aug 16, 2013 at 6:06

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the reference, but I'm rather interested in the case where the encoding is "classical" (i.e. not succint). $\endgroup$
    – Florent Foucaud
    Oct 31, 2013 at 11:04
-1
$\begingroup$

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}|)$.

Improve this answer
$\endgroup$
6
  • $\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$
    – Florent Foucaud
    Jul 16, 2013 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, 2013 at 13:57
  • $\begingroup$ @Matteo: I don't thing this works, sure you use the correct def of VC? $\endgroup$
    – domotorp
    Jul 16, 2013 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, 2013 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$
    – Florent Foucaud
    Jul 16, 2013 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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