# “Almost easy” NP-complete problems

Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs.

In other words, there is an $A\in$ P, such that $L\Delta A$ is vanishing, which means $$\lim_{n\rightarrow\infty} \frac{|(L\Delta A) \cap \{0,1\}^n|}{2^n}=0.$$ It also means that on a uniform random input, the polytime algorithm for $A$ will give the correct answer for $L$ with probability approaching 1. Therefore, it makes sense to view $L$ almost easy.

Note that $L\Delta A$ does not have to be sparse. For example, if it has $2^{n/2}$ $n$-bit strings, then it is still vanishing (at an exponential rate), since $2^{n/2}/2^n=2^{-n/2}$.

It is not hard to (artificially) construct NP-complete problems that are P-density-close, according to the above definition. For example, let $L$ be any NP-complete language, and define $L^2=\{xx\,|\, x\in L\}$. Then $L^2$ retains NP-completeness, but has at most $2^{n/2}$ $n$-bit yes-instances. Therefore, the trivial algorithm that answers "no" to every input, will correctly decide $L^2$ on almost all inputs; it will err only on a $\leq 1-2^{-n/2}$ fraction of $n$-bit inputs.

On the other hand, it would be very surprising if all NP-complete problems are P-density-close. It would mean that, in a sense, all NP-complete problems are almost easy. This motivates the question:

Assuming P$\neq$NP, which are some natural NP-complete problems that are not P-density-close?

• Since Heuristica is not ruled out, there is not even a not-necessarily-natural problem for which P≠NP is known to imply that the problem is not almost in P. ​ ​ – user6973 Nov 15 '15 at 6:26
• I believe that the post correspondence problems is a good candidate problem. It is hard even for uniformly random instances and hence it is hard in the average-case. – Mohammad Al-Turkistany Nov 15 '15 at 12:29
• FYI: Your choice of nomenclature, while natural, conflicts with some existing nomenclature: The class Almost-P consists of those languages L such that $\{A : L \in P^A\}$ has measure 1. You might also be interested to know that the sparse version of your definition has already been used and has connections to several other ideas, see P-close. Given the defn of P-close, maybe a good name for your concept is P-density-close, or P-close-enough :). – Joshua Grochow Nov 15 '15 at 14:26
• On the other hand, the "Graph Coloration" decision problem is presumably a candidate for such a problem. $\;$ – user6973 Nov 15 '15 at 19:02
• I'm not convinced this is the right definition. If the density of $L$ vanishes then it is "almost easy" via any trivial language $A$, no matter how hard it actually is. Yet it is difficult to exhibit natural hard languages over alphabet $\{0,1\}$ with density that does not vanish, simply because of encoding. Should the intersection not be with the size $n$ valid inputs (so this is a promise problem), rather than all strings? Otherwise, this mainly requires answering the question: is there a Boolean encoding of some NP-hard language with density that does not vanish? – András Salamon Nov 16 '15 at 12:02

Interestingly, the most "standard" hypotheses do not seem to imply it. That is, it does not appear to follow (unless I overlooked something) from P$\neq$NP, P$=$BPP, NP$\neq$coNP, E$\neq$NE, EXP$\neq$NEXP, NP$\neq$PSPACE, NP$\neq$EXP, NP$\not\subseteq$P/poly, PH does not collapse, etc.
On the other hand, I found one, slightly less standard, hypothesis, which does imply the existence of the sought NP-complete problem, albeit not a natural one. In the theory of resource bounded measure the fundamental hypothesis is that NP does not have $p$-measure zero, denoted by $\mu_p($NP$)\neq 0$. Informally, this means that NP-languages within E do not form a negligible subset. For details, see a survey here. In this theory they prove, among many other things, that $\mu_p($NP$)\neq 0$ implies the existence of a P-bi-immune language in NP. A language $L$ is P-bi-immune if neither $L$ nor its complement has an infinite subset in P. Such a language satisfies our requirement in a strong way.