<p>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:</p>

<p><em>On the Complexity of Approximating the VC Dimension</em>
<a href="http://users.cms.caltech.edu/~umans/papers/MU01-final.ps" rel="nofollow">http://users.cms.caltech.edu/~umans/papers/MU01-final.ps</a></p>

CC BY-SA 3.0
2013-10-31T11:04:09.610Z
Thanks for the reference, but I'm rather interested in the case where the encoding is "classical" (i.e. not succint).
Florent Foucaud
CC BY-SA 3.0
2013-10-16T15:09:51.113Z
2013-10-16T15:09:51.113Z
Andy Drucker
<p>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}|)$.</p>

CC BY-SA 3.0
2013-07-16T09:51:44.167Z
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|)})$...
Florent Foucaud
CC BY-SA 3.0
2013-07-16T13:57:20.503Z
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.
Matteo
CC BY-SA 3.0
2013-07-16T13:59:22.473Z
@Matteo: I don't thing this works, sure you use the correct def of VC?
domotorp
CC BY-SA 3.0
2013-07-16T15:02:55.767Z
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}$.
Matteo
CC BY-SA 3.0
2013-07-16T16:09:16.067Z
@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.
Florent Foucaud
CC BY-SA 3.0
2013-07-16T16:55:30.780Z
Ok I see your point. I thought we could avoid going "into" the elements of $\mathcal{S}$, but now I see that it's not possible. Sorry for the noise.
Matteo
CC BY-SA 3.0
2013-07-08T15:14:02.333Z
2013-07-08T15:14:02.333Z
Matteo
<p>The <a href="http://en.wikipedia.org/wiki/VC_dimension">Vapnik-Chervonenkis dimension</a> 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$.</p>

<p>The following decision problem is then natural:</p>

<blockquote>
  <p><strong>VC DIMENSION</strong><br>
  <strong>Input:</strong> a set system $(X,\mathcal S)$ and an integer $k$.<br>
  <strong>Task:</strong> decide whether the VC dimension of $(X,\mathcal S)$ is at least $k$.</p>
</blockquote>

<p>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 <a href="http://dx.doi.org/10.1006/jcss.1996.0058">here</a>). However, I wonder whether something is known for the following specific case:</p>

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

CC BY-SA 3.0
2013-08-16T06:06:50.330Z
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.
Sariel Har-Peled
<cc.complexity-theory><reference-request><vc-dimension><set-system>
The complexity of recognizing optimal set systems for the V-C dimension
Florent Foucaud
# The complexity of recognizing optimal set systems for the V-C dimension

(Asked by: username_0 on 2013-07-08)

The [Vapnik-Chervonenkis dimension](http://en.wikipedia.org/wiki/VC_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](http://dx.doi.org/10.1006/jcss.1996.0058)). 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|)$?

**Tags:** cc.complexity-theory, reference-request, vc-dimension, set-system
> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2013-10-16. Score: 1

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>

> **Comments:**
> **username_0**: Thanks for the reference, but I'm rather interested in the case where the encoding is "classical" (i.e. not succint).  

---

### Answer by username_3 on 2013-07-08. Score: -1

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

> **Comments:**
> **username_0**: 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|)})$...  
> **username_3**: 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.  
> **username_4**: @Matteo: I don't thing this works, sure you use the correct def of VC?  
> **username_3**: 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}$.  
> **username_0**: @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.  
> **username_3**: Ok I see your point. I thought we could avoid going "into" the elements of $\mathcal{S}$, but now I see that it's not possible. Sorry for the noise.  

---

