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?

  • 2
    $\begingroup$ Almost every random graph contains a copy of $K_4$, and hence is NOT 3-colorable. Hence GRAPH-3-COLORABILITY is an NP-complete problem with property (P). $\endgroup$
    – Gamow
    Commented Jan 19, 2022 at 9:26
  • 1
    $\begingroup$ @Gamow Yes, but I am looking for problems where these properties are assumed not to hold. $\endgroup$
    – Punga
    Commented Jan 19, 2022 at 9:35
  • 1
    $\begingroup$ Aah, then you should read about "average case hardness". $\endgroup$
    – Gamow
    Commented Jan 19, 2022 at 10:21
  • 1
    $\begingroup$ @Gamow That's where I got the construction for the "artificial" construction of a NP-complete L with (P). But does average complexity being superpolynomial imply not(P)? That doesn't look obvious to me. $\endgroup$
    – Punga
    Commented Jan 19, 2022 at 10:28
  • 1
    $\begingroup$ In the definition of P', do you really mean $=1-\epsilon$ rather than, say, $\ge1-\epsilon$? That's a tall order. There are only countably manu Turing machines, but uncountably many $\epsilon\in(0,1)$, hence taken literally, this can never hold. $\endgroup$ Commented Jan 19, 2022 at 13:00

1 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=

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.

  • 1
    $\begingroup$ Your second result includes as a special case the first result, even without the paddability assumption. Is that correct? $\endgroup$ Commented Jan 21, 2022 at 7:58
  • $\begingroup$ Can you give references for these results? $\endgroup$ Commented Jan 21, 2022 at 8:03
  • $\begingroup$ @EmilJeřábek Yes, the second result includes the first, since a paddable NP-complete language is also NP-hard. Just the proof is different, see the first referenced paper, top of page 188. The two papers mentioned in the answer, with links to pdf full text, serve as references, and provide further pointers. $\endgroup$ Commented Jan 21, 2022 at 15:31

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.