MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How small can a language in $NP$ but not in $P$ be? Of course, I don't expect a proof that there exists a language in $NP\setminus P$, so instead I'll ask: Can we rule out any of these conjectures?

1) There is a language $NP\setminus P$, where all elements are on the form $0^{2^{2^{\dots ^2}}}$.

2) For any infinite language $A\in P$ there is $B\subset A$ in $NP\setminus P$.

share|cite|improve this question
Perhaps I asked the question the wrong way around. I am hoping for an answer that says that we cannot rule out these results from what we know today. E.g. "open conjecture X would imply your conjecture i" (or not i) – Sune Jakobsen May 18 '12 at 11:18
We do not know that there are any languages in NP - P, so we can't rule out anything – David Harris May 18 '12 at 14:04
@David: It might be possible to show that one of the above conjectures are false, without deciding P vs NP. – Sune Jakobsen May 18 '12 at 14:10
I say try asking this on . – Zsbán Ambrus May 18 '12 at 16:14

This doesn't specifically address (1) or (2), but let me instead try to answer the title question of how small a set in NP-P can be.

Definition. The asymptotic density of a language $L$, a set of strings in a finite alphabet $\Sigma$, is the limit $$\lim_{n\to\infty}\frac{|L\cap \Sigma^n|}{|\Sigma^n|},$$ if this limit exists. This is the limit of the proportion of all strings of length $n$ in the language, as $n$ increases.

Theorem. If $P\neq NP$, then there is a language $A\in NP-P$ with asymptotic density zero. Indeed, there are such $A$ of any prescribed density, or non-density.

Proof. Let $A$ be all instances of the 3-Sat problem (or some other NP complete problem), but only for instances where each clause is repeated twice in a row. Note that $A$ remains NP complete, since given any instance $p$ of 3-Sat, I may form a new equivalent instance $p^\ast$ by doubling every clause, and then ask whether $p^\ast$ is in $A$. This is a polynomial time reduction, since $p^\ast$ is only about twice as large as $p$. But meanwhile, the asymptotic density of $A$ is zero, since most strings will not have this double-clause feature. (One can similarly use padding for many other NP complete problems).

To achive some other density, one can take the disjoint union of a P problem of known density with A, so that the combined set of strings will still be NP complete, but it inherit the density of the P problem. QED

share|cite|improve this answer
Ladner's result on the existence of infinitely many languages of varying complexity in NP - P if there is at least one might also be relevant. Gerhard "Ask Me About System Design" Paseman, 2012.05.18 – Gerhard Paseman May 19 '12 at 4:50
  1. To have a set $A\subseteq \{2\Uparrow n \mid n\in \mathbb N \}$ s.t. $A\in \mathsf{NP} -\mathsf{P}$, it suffices to have a set $A' \in \mathsf{NTime}(2\Uparrow n) - \mathsf{DTime}(2\Uparrow n)$ and let $A = \{ 2\Uparrow k \mid k \in A'\}$, which is consistent with current state of knowledge (AFAIK). So conjecture 1 cannot be ruled out unless this possibility is ruled out.

  2. Assuming that $\mathsf{P} \neq \mathsf{NP}$, the statement is true if $A$ is not just polynomial time decidable but also polynomial time enumerable. (Take a set in $\mathsf{NP}-\mathsf{P}$ and consider its image under the enumeration inside $A$. The image is in $\mathsf{NP}-\mathsf{P}$ and is a subset of $A$ as required.) Note that any r.e. set is in fact polynomial time enumerable (the enumeration doesn't need to be injective). Therefore if $\mathsf{NP}\neq \mathsf{P}$ then conjecture 2 will be true and cannot be ruled out.

share|cite|improve this answer
But conjecture 1 is a special case of 2. If NP!=P implies conjecture 2, then both conjectures and NP!=P are all equivalent. I doubt that. – Sune Jakobsen Jun 1 '12 at 6:32
@Sune, I don't see how 1 is a special case of 2. 2 doesn't seem to imply one. (Do you have a proof or is it just some intuition?) – Kaveh Jun 2 '12 at 4:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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