# How small can a language in NP\P be?

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

-
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 cstheory.stackexchange.com . –  Zsbán Ambrus May 18 '12 at 16:14

## 2 Answers

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

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

-
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