# How can we compute the VC dimension of a finite class of sets?

Let $$F$$ be a class of subsets of a finite set $$X$$ of cardinality $$n$$. What is the complexity of computing the VC dimension of $$F$$? Can we do better than looping through every subset of $$X$$ and checking if $$F$$ shatters it?

In 1996 Papadimitriou and Yannakakis noted that there exists an $$n^{O(\log n)}$$ brute-force algorithm (where $$n$$ is the size of the input) for computing VC-dimension of a 0-1 matrix by checking all the subsets of size up to the trivial bound, the logarithm of the number of hypotheses.
• I'm a noob so I could be wrong, but didn't the PY1996 paper just note there's an $n^{O(\log n)}$ algorithm, since one only needs to check if subsets of size at most $\lceil \log_2 n \rceil$ are shattered? Nov 6, 2021 at 14:46
• Is the $n$ in your answer the cardinality of what I call $X$, or the cardinality of what I call $F$? Nov 7, 2021 at 8:57
• @JackM here $n$ is the size of the input, which I take to be the number of entries in the input matrix. Nov 7, 2021 at 14:49