<p>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$. </p>

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

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

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

CC BY-SA 3.0
2011-06-09T07:06:57.583Z
[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
CC BY-SA 3.0
2011-06-09T13:57:09.863Z
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
CC BY-SA 3.0
2011-06-09T15:15:22.483Z
Thanks András, your comment is incorporated in the answer.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-06-09T16:01:27.860Z
@Mohammad: make the lower bound $2^{\omega(\log n)}$, or $n^{\omega(1)}$: that's what superpolynomial means.
Sasho Nikolov
CC BY-SA 3.0
2011-06-09T16:46:10.740Z
@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
CC BY-SA 3.0
2011-06-09T16:52:13.440Z
@Mohammad: sorry, i was not aware of this. You might want to include the references (Mahaney and Buhrman-Hitchcock) in the answer
Sasho Nikolov
CC BY-SA 3.0
2011-06-09T06:26:27.697Z
2011-06-09T19:51:47.443Z
2011-06-09T19:51:47.443Z
Mohammad Al-Turkistany
<p>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 <a href="http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf">http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf</a> .</p>

CC BY-SA 3.0
2011-06-09T08:30:43.487Z
2011-06-09T08:30:43.487Z
Bart Jansen
<p>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? </p>

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

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

<p>Here is a reference on NP-hardness of membership testing for unit disk graphs:
<a href="http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf" rel="nofollow">http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf</a></p>

CC BY-SA 3.0
2011-06-09T16:04:04.257Z
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
CC BY-SA 3.0
2011-06-09T22:13:45.507Z
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
<cc.complexity-theory><graph-theory>
Can I bound the cardinality of a set if testing for membership in it is known to be NP-complete?
David Choi
# Can I bound the cardinality of a set if testing for membership in it is known to be NP-complete?

(Asked by: username_0 on 2011-06-09)

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>

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: Thank you for your kind assistance. Both answers were helpful and insightful; I would have accepted either one in the absence of the other.  

---

## 2 answers

### Answer by username_5 on 2011-06-09. Score: 11 | Accepted answer

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> .


---

### Answer by username_2 on 2011-06-09. Score: 13

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

> **Comments:**
> **username_3**: [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.  
> **username_4**: 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.  
> **username_2**: Thanks András, your comment is incorporated in the answer.  
> **username_1**: @Mohammad: make the lower bound $2^{\omega(\log n)}$, or $n^{\omega(1)}$: that's what superpolynomial means.  
> **username_2**: @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  
> **username_1**: @Mohammad: sorry, i was not aware of this. You might want to include the references (Mahaney and Buhrman-Hitchcock) in the answer  

---

