4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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) $\endgroup$ May 18, 2012 at 11:18
  • $\begingroup$ We do not know that there are any languages in NP - P, so we can't rule out anything $\endgroup$ May 18, 2012 at 14:04
  • 2
    $\begingroup$ @David: It might be possible to show that one of the above conjectures are false, without deciding P vs NP. $\endgroup$ May 18, 2012 at 14:10
  • $\begingroup$ I say try asking this on cstheory.stackexchange.com . $\endgroup$ May 18, 2012 at 16:14

2 Answers 2

5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ May 19, 2012 at 4:50
0
$\begingroup$
  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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jun 1, 2012 at 6:32
  • $\begingroup$ @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?) $\endgroup$
    – Kaveh
    Jun 2, 2012 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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