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

anylanguages in NP - P, so we can't rule out anything – David Harris May 18 '12 at 14:04