Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?

Question

I am wondering about the following property $\text{(P)}$ of an $NP$-complete language $L$

$\begin{align}\exists M\text{ a polytime machine}\lim_{n\to\infty}P(\text{M solves a random instance of size $n$})=1.\tag{P}\end{align}$

At first glance the property holding for some $NP$-complete problem looks unlikely, but it is possible to construct from any $NP$-complete language $L$ another $NP$-complete lanaguage $$L'=\{1^nw;w\in L, n=\ell(w)\}\cup\{w'w;\ell(w')=\ell(w)=n,w'\not=1^n\}$$ which has the property $(\text{P})$ because only $1$ in $2^n$ instances is actually non-trivial.

Let me propose another property $\text{(P')}$

$\begin{align}\forall \varepsilon>0\exists M\text{ $p$-time}\lim_{n\to\infty}P(\text{M solves a random instance of size $n$})\geq1-\epsilon.\tag{P'}\end{align}$

Now my question is, are there some natural $NP$-complete languages $L$, where it is common to assume that either $(\text{P})$ or $(\text{P'})$ is not true? More generally, does there exists some concrete conjecture implying this?

Answer 1

Let us define the distance function of two languages $L, L'$ as $$ dist(n)= |L\Delta L'|_n$$ which means the number of $n$-bit strings in the symmetric difference $L\Delta L'$.

If property ${\text P}$ in the question holds for an ${\bf NP}$-complete language $L$, it would mean: there exists a language $L'\in {\bf P}$, such that $$\lim_{n\rightarrow\infty}\frac{dist(n)}{2^n}=0. \;\;\;\;\;\;\;\;\;\;\;\;\; (*)$$ In other words, $L$ could be well approximated by a polynomial time algorithm, in the sense that the latter makes mistakes only on a vanishing set.

Related questions have been investigated in the literature, see e.g., Fu, "On Lower Bounds of the Closeness Between Complexity Classes" and Glaser, Pavan, Selman, Sengupta, "Properties of NP-complete sets" (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.9772&rep=rep1&type=pdf)

Some known results are:

• If for a paddable $\bf NP$-complete language $L$ there is an $L'\in {\bf P}$, such that $dist(n)$ is polynomially bounded, then ${\bf P}={\bf NP}$. (Note that all known natural $\bf NP$-complete languages are paddable.)

• If for an $\bf NP$-hard language $L$ there is an $L'\in {\bf P}$, such that $dist(n)$ is polynomially bounded, then ${\bf P}={\bf NP}$. ($L$ is not required to be in $\bf NP$.)

• If for a paddable $\bf NP$-complete language $L$ there is an $L'\in {\bf P}$, such that $dist(n)$ is quasi-polynomially bounded, i.e., $dist(n)=O(2^{\log^c n})$ for some $c>0$, then ${\bf NP}={\bf RP}$.

There are more such results, but similarly to the above, they all use a stronger approximation condition than $(*)$, since $(*)$ would still allow an exponentially growing $dist(n)$, such as $2^{n/2}$.

Therefore, it seems, the problem you raise is open: there appears to be no known conjecture that would exclude a polynomial time approximation to every (or at least every natural) $\bf NP$-complete language in the sense of $(*)$, i.e., with vanishing error rate, but without specifying how fast it vanishes.