<p>Let us define the distance function of two languages <span class="math-container">$L, L'$</span> as
<span class="math-container">$$ dist(n)= |L\Delta L'|_n$$</span>
which means the number of <span class="math-container">$n$</span>-bit strings in the symmetric difference
<span class="math-container">$L\Delta L'$</span>.</p>
<p>If property <span class="math-container">${\text P}$</span> in the question holds for an <span class="math-container">${\bf NP}$</span>-complete language <span class="math-container">$L$</span>, it would mean: there exists a language <span class="math-container">$L'\in {\bf P}$</span>, such that <span class="math-container">$$\lim_{n\rightarrow\infty}\frac{dist(n)}{2^n}=0. \;\;\;\;\;\;\;\;\;\;\;\;\; (*)$$</span>
In other words, <span class="math-container">$L$</span> could be well approximated by a polynomial time algorithm, in the sense that the latter makes mistakes only on a vanishing set.</p>
<p>Related questions have been investigated in the literature, see e.g., <a href="https://link.springer.com/content/pdf/10.1007/BF01202282.pdf" rel="nofollow noreferrer">Fu, &quot;On Lower Bounds of the Closeness Between Complexity Classes&quot;</a> and
Glaser, Pavan, Selman, Sengupta, &quot;Properties of NP-complete sets&quot;
(<a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.9772&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.9772&amp;rep=rep1&amp;type=pdf</a>)</p>
<p>Some known results are:</p>
<ul>
<li><p>If for a paddable <span class="math-container">$\bf NP$</span>-complete language <span class="math-container">$L$</span> there is an <span class="math-container">$L'\in {\bf P}$</span>, such that <span class="math-container">$dist(n)$</span> is polynomially bounded, then <span class="math-container">${\bf P}={\bf NP}$</span>. (Note that all known <em>natural</em> <span class="math-container">$\bf NP$</span>-complete languages are paddable.)</p>
</li>
<li><p>If for an <span class="math-container">$\bf NP$</span>-hard language <span class="math-container">$L$</span> there is an <span class="math-container">$L'\in {\bf P}$</span>, such that <span class="math-container">$dist(n)$</span> is polynomially bounded, then <span class="math-container">${\bf P}={\bf NP}$</span>. (<span class="math-container">$L$</span> is not required to be in <span class="math-container">$\bf NP$</span>.)</p>
</li>
<li><p>If for a paddable <span class="math-container">$\bf NP$</span>-complete language <span class="math-container">$L$</span> there is an <span class="math-container">$L'\in {\bf P}$</span>, such that <span class="math-container">$dist(n)$</span> is quasi-polynomially bounded, i.e., <span class="math-container">$dist(n)=O(2^{\log^c n})$</span> for some <span class="math-container">$c&gt;0$</span>, then <span class="math-container">${\bf NP}={\bf RP}$</span>.</p>
</li>
</ul>
<p>There are more such results, but similarly to the above, they all use a stronger approximation condition than <span class="math-container">$(*)$</span>, since <span class="math-container">$(*)$</span> would still allow an exponentially growing <span class="math-container">$dist(n)$</span>, such as <span class="math-container">$2^{n/2}$</span>.</p>
<p>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) <span class="math-container">$\bf NP$</span>-complete language in the sense of <span class="math-container">$(*)$</span>, i.e., with vanishing error rate, but without specifying how fast it vanishes.</p>

CC BY-SA 4.0
2022-01-21T07:58:26.193Z
Your second result includes as a special case the first result, even without the paddability assumption. Is that correct?
Emil Jeřábek
CC BY-SA 4.0
2022-01-21T08:03:43.927Z
Can you give references for these results?
Emil Jeřábek
CC BY-SA 4.0
2022-01-21T15:31:32.617Z
@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.
Andras Farago
CC BY-SA 4.0
2022-01-20T20:30:28.460Z
2022-01-20T20:30:28.460Z
Andras Farago
<p>I am wondering about the following property <span class="math-container">$\text{(P)}$</span> of an <span class="math-container">$NP$</span>-complete language <span class="math-container">$L$</span></p>
<p><span class="math-container">$\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}$</span></p>
<p>At first glance the property holding for some <span class="math-container">$NP$</span>-complete problem looks unlikely, but it is possible to construct from any <span class="math-container">$NP$</span>-complete language <span class="math-container">$L$</span> another <span class="math-container">$NP$</span>-complete lanaguage <span class="math-container">$$L'=\{1^nw;w\in L, n=\ell(w)\}\cup\{w'w;\ell(w')=\ell(w)=n,w'\not=1^n\}$$</span> which has the property <span class="math-container">$(\text{P})$</span> because only <span class="math-container">$1$</span> in <span class="math-container">$2^n$</span> instances is actually non-trivial.</p>
<p>Let me propose another property <span class="math-container">$\text{(P')}$</span></p>
<p><span class="math-container">$\begin{align}\forall \varepsilon&gt;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}$</span></p>
<p>Now my question is, are there some natural <span class="math-container">$NP$</span>-complete languages <span class="math-container">$L$</span>, where it is common to assume that either <span class="math-container">$(\text{P})$</span> or <span class="math-container">$(\text{P'})$</span> is not true? More generally, does there exists some concrete conjecture implying this?</p>

CC BY-SA 4.0
2022-01-19T09:26:27.227Z
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).
Gamow
CC BY-SA 4.0
2022-01-19T09:35:40.883Z
@Gamow Yes, but I am looking for problems where these properties are assumed not to hold.
Punga
CC BY-SA 4.0
2022-01-19T10:21:22.537Z
Aah, then you should read about "average case hardness".
Gamow
CC BY-SA 4.0
2022-01-19T10:28:22.013Z
@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.
Punga
CC BY-SA 4.0
2022-01-19T13:00:17.130Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-01-19T13:54:18.317Z
@EmilJeřábek thanks, edited.
Punga
CC BY-SA 4.0
2022-01-20T10:53:50.933Z
What about: "Given number $n$; does $n$ have exactly $\log \log n$ distinct prime factors?" (not NPC but in NP) , see  [Erdos-Kac theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem)
Marzio De Biasi
<randomness><np-complete><hard-instances><complexity-assumptions>
Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?
Punga
# Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?

(Asked by: username_0 on 2022-01-19)

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?

**Tags:** randomness, np-complete, hard-instances, complexity-assumptions

> **Comments:**
> **username_1**: 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).  
> **username_0**: @username_1 Yes, but I am looking for problems where these properties are assumed not to hold.  
> **username_1**: Aah, then you should read about "average case hardness".  
> **username_0**: @username_1 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.  
> **username_2**: 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.  
> **username_0**: @EmilJeřábek thanks, edited.  
> **username_3**: What about: "Given number $n$; does $n$ have exactly $\log \log n$ distinct prime factors?" (not NPC but in NP) , see  [Erdos-Kac theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem)  

---

## 1 answers

### Answer by username_4 on 2022-01-20. Score: 2 | Accepted answer

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"](https://link.springer.com/content/pdf/10.1007/BF01202282.pdf) 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.

> **Comments:**
> **username_2**: Your second result includes as a special case the first result, even without the paddability assumption. Is that correct?  
> **username_2**: Can you give references for these results?  
> **username_4**: @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.  

---

