# Can I bound the cardinality of a set if testing for membership in it is known to be NP-complete?

I would like to have a bound on the cardinality of the set of unit disk graphs with $N$ vertices. It is known that checking whether a graph is a member of this set is NP-hard. Does this lead to any lower bound on the cardinality, assuming P $\neq$ NP?

For example, suppose there is an ordering on all graphs with $N$ vertices. Would NP-hardness then imply the cardinality exceeds $2^N$, in that otherwise you could test for membership in polynomial time by doing a binary search through the set? I think this would assume that you have somehow stored the set in memory... Is this allowed?

Defintion: A graph is a unit disk graph if each vertex can be associated with a unit disk in the plane, such that vertices are connected whenever their disks intersect.

Here is a reference on NP-hardness of membership testing for unit disk graphs: http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf

• I am wondering, is there an example where this technique provides the best known lower bound on the size of some set? That would be a cool indirect combinatorial application of complexity theory. – Sasho Nikolov Jun 9 '11 at 16:04
• Thank you for your kind assistance. Both answers were helpful and insightful; I would have accepted either one in the absence of the other. – David Choi Jun 9 '11 at 22:13

I'm not sure if you're asking this question for the technique or for the answer, but there is a recent paper by McDiarmid and Mueller where they show the number of (labeled) unit-disk graphs on $n$ vertices is $2^{(2 + o(1))n}$; see http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf .

Mahaney’s Theorem states that sparse NP-complete sets exist iff P=NP. Therefore, assuming $P \neq NP$ implies a super-polynomial lower bound on the number of instances of size $n$ in $NP$-complete sets, for infinitely many $n$. That is, if $P \neq NP$, then any $NP$-complete set must have some $\epsilon \gt 0$ such that for infinitely-many integers $n\ge 0$, the set contains at least $2^{n^{\epsilon}}$ strings of length $n$.

H. Buhrman and J. M. Hitchcock proved the lower bound ($2^{n^{\epsilon}}$) is tight, unless the polynomial hierarchy collapses.

[1] H. Buhrman and J. M. Hitchcock, NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly, In IEEE Conference on Computational Complexity, pages 1–7, 2008

[2] Eric Allender, A Status Report on the P Versus NP Question, Advances in Computers, Volume 77, 2009, Pages 117-147

• [Mah82] S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis, Journal of Computer and System Sciences 25:130-143, 1982. – Marzio De Biasi Jun 9 '11 at 7:06
• Each NP-complete set has countably infinite cardinality. You probably meant that P≠NP implies a super-polynomial lower bound on the number of instances of size $n$, for infinitely many $n$. Note also that $2^{(\log n)^2}$ is super-polynomial without being of the form you give. – András Salamon Jun 9 '11 at 13:57
• Thanks András, your comment is incorporated in the answer. – Mohammad Al-Turkistany Jun 9 '11 at 15:15
• @Mohammad: make the lower bound $2^{\omega(\log n)}$, or $n^{\omega(1)}$: that's what superpolynomial means. – Sasho Nikolov Jun 9 '11 at 16:01
• @Sasho, H. Buhrman and J. M. Hitchcock proved the lower bound ($2^{n^{\epsilon}}$) I mentioned in my answer, unless the polynomial hierarchy collapses. H. Buhrman and J. M. Hitchcock, NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly, In IEEE Conference on Computational Complexity, pages 1–7, 2008 – Mohammad Al-Turkistany Jun 9 '11 at 16:46