<p>I looked into whether there is a generally accepted hypothesis in complexity theory, which implies that there must exist an <strong>NP</strong>-complete language that cannot be accepted in polynomial time on almost all inputs (as defined in the question).</p>

<p>Interestingly, the most "standard" hypotheses do not seem to imply it. That is, it does not appear to follow (unless I overlooked something) from <strong>P</strong>$\neq$<strong>NP</strong>, <strong>P</strong>$=$<strong>BPP</strong>,
<strong>NP</strong>$\neq$<strong>coNP</strong>, <strong>E</strong>$\neq$<strong>NE</strong>, <strong>EXP</strong>$\neq$<strong>NEXP</strong>, <strong>NP</strong>$\neq$<strong>PSPACE</strong>,  <strong>NP</strong>$\neq$<strong>EXP</strong>, <strong>NP</strong>$\not\subseteq$<strong>P</strong>/poly, <strong>PH</strong> does not collapse,  etc.</p>

<p>On the other hand, I found one, slightly less standard, hypothesis, which does imply the existence of the sought <strong>NP</strong>-complete problem, albeit not a natural one.  In the theory of <a href="https://en.wikipedia.org/wiki/Resource_bounded_measure" rel="noreferrer">resource bounded measure</a> the fundamental hypothesis is that <strong>NP</strong> does not have $p$-measure zero, denoted by 
$\mu_p($<strong>NP</strong>$)\neq 0$. Informally, this means that <strong>NP</strong>-languages within <strong>E</strong> do not form a negligible subset. For details, see a survey <a href="http://web.cs.iastate.edu/~lutz/=PAPERS/tprbm-eatcs.pdf" rel="noreferrer">here</a>. In this theory they prove, among many other things,  that 
$\mu_p($<strong>NP</strong>$)\neq 0$ implies the existence of a <strong>P</strong>-bi-immune language in <strong>NP</strong>. A language $L$ is <strong>P</strong>-bi-immune if  neither $L$ nor its complement has an infinite subset in <strong>P</strong>. Such a language satisfies our requirement in a strong way.</p>

<p>However, it still remains unclear whether an example exists that represents a <em>natural</em> problem. </p>

CC BY-SA 3.0
2015-11-18T05:07:21.460Z
Bi-immunity is also *much* stronger than your condition, and is related to the more common usage of "almost all" in structural complexity theory, namely "for all but finitely many"...
Joshua Grochow
CC BY-SA 3.0
2015-11-18T13:22:31.703Z
@JoshuaGrochow I agree, but it appears that, in a sense, P-bi-immunity means   _too strong_  intractability. It does not seem to occur among natural NP-complete problems. It is surprising to me that apparently there is no result that provides conditions merely for the existence of a "weakly almost everywhere" intractable NP-complete language. By "weakly almost everywhere" I mean that the "all but finitely many" condition is replaced by "all but vanishingly many." That might relate  better to what is really encountered in practice.
Andras Farago
CC BY-SA 3.0
2015-12-11T21:26:12.050Z
@RickyDemer As far as I know, it is not known whether NP is                          p-measurable.
Andras Farago
CC BY-SA 3.0
2015-11-18T03:17:47.090Z
2015-11-18T03:17:47.090Z
Andras Farago
<p>Let us say that a language $L$ is <strong>P</strong>-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs. </p>

<p>In other words, there is an  $A\in$ <strong>P</strong>, 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$ <em>almost easy.</em></p>

<p>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}$.</p>

<p>It is not hard to (artificially) construct <strong>NP</strong>-complete problems  that are  <strong>P</strong>-density-close, according to the above definition. For example, let $L$ be any <strong>NP</strong>-complete language, and define $L^2=\{xx\,|\, x\in L\}$. Then $L^2$ retains <strong>NP</strong>-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.</p>

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

<blockquote>
  <p>Assuming <strong>P</strong>$\neq$<strong>NP</strong>, which are some  <em>natural</em> <strong>NP</strong>-complete problems that are <em><strong>not</strong></em>  <strong>P</strong>-density-close? </p>
</blockquote>

CC BY-SA 3.0
2015-11-15T12:29:36.963Z
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
CC BY-SA 3.0
2015-11-15T14:26:18.763Z
FYI: Your choice of nomenclature, while natural, conflicts with some existing nomenclature: The class [Almost-P](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:A#almostp) 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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pclose). Given the defn of P-close, maybe a good name for your concept is P-density-close, or P-close-enough :).
Joshua Grochow
CC BY-SA 3.0
2015-11-15T14:43:22.290Z
@JoshuaGrochow Thank you, I edited the question, using one of your recommended names, to avoid conflicting with existing terminology.
Andras Farago
CC BY-SA 3.0
2015-11-16T12:02:28.597Z
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
CC BY-SA 3.0
2015-11-16T21:50:09.897Z
It seems that the right formalism of your intuition is the notion of [Generic-case complexity] (http://www.wikipedia.org/wiki/Generic-case_complexity).
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-11-17T04:16:07.800Z
@AndrásSalamon One can construct NP-complete languages with non-vanishing density. For example, let $L$ contain those graphs that have a half-clique (a clique on $\geq n/2$ vertices) **or** have an odd number of edges. This contains more than half of all $n$-vertex graphs, yet it remains  hard, because to decide membership in $L$, we have to be able to decide half-clique on graphs with an even number of edges, which is still hard. On the other hand, $L$ is solvable in polynomial time on almost all inputs (just return the parity of the number of edges).
Andras Farago
CC BY-SA 3.0
2015-11-17T04:20:54.857Z
@AndrasFarago how are you encoding graphs with alphabet $\{0,1\}$?
András Salamon
CC BY-SA 3.0
2015-11-17T04:38:59.990Z
@AndrásSalamon Let us use labeled graphs. Then each $(n^2-n)/2$ long binary string uniquely encodes  the upper half of the adjacency matrix of an $n$-vertex labeled graph, and so the graph itself.
Andras Farago
CC BY-SA 3.0
2015-11-17T04:46:37.587Z
@MohammadAl-Turkistany You may be right, I am not familiar with generic case complexity. But it still appears different, as they say: "An algorithm is in GenP (generically polynomial time) if it never gives incorrect answers and if it gives correct answers in polynomial time on a generic set of inputs." This seems different from what I asked for, since I do allow that the algorithm gives incorrect answer, just "rarely." But it is conceivable that the two concepts may be equivalent.
Andras Farago
CC BY-SA 3.0
2015-11-17T06:20:17.887Z
@AndrasFarago OK, but isn't your half-clique/odd-edges example rather unnatural?  The only reason its density doesn't vanish is because an easy language has been adjoined to bolster it.  I'm still trying to find a natural language that is hard and does not have vanishing density.  This seems to be the core of your question, even if one restricts attention to the ratio of yes-instances to valid inputs.
András Salamon
CC BY-SA 3.0
2015-11-17T13:52:06.517Z
@AndrásSalamon I agree that artificially adjoining an easy set, just to beef up the density, may be viewed as unnatural. But even if a truly natural    NP-complete language is exhibited with a non-vanishing set of                      yes-instances, it may still be hard to prove that there is no way to shave off an easy set from it, such that the remaining yes-instances already constitute a vanishing set.
Andras Farago
CC BY-SA 3.0
2015-11-17T16:20:03.960Z
@AndrasFarago Agreed that it is not enough.  However, bounded treewidth and other natural restrictions of graphs to ensure polynomial-time algorithms yield nowhere dense classes.  These seem to have vanishing density in the sense used here, even though they have superpolynomial density.  So to me the first key part of your question seems to be whether there are actually any natural, hard languages that have non-vanishing density.  (Also, the usual meaning of "dense" is $2^{n^\varepsilon}$ in the size-$n$ instances, for some $\varepsilon > 0$, so perhaps this is a kind of "linear density".)
András Salamon
CC BY-SA 3.0
2015-11-17T16:53:50.183Z
all this reminds me; it would be nice if someone did a survey in this area & covered (1) mahaneys theorem (2) (NP complete) slice functions for monotone circuits (3) hartmanis-stearns isomorphism conjecture. these seem to be the main areas in the literature that attack P vs NP from the angle of "density". (oh yeah, natural proofs also.) they all seem to be connected but there is little tieing it all together... think all relate to your question but the details would be subtle to elaborate/ articulate... also rossmans results on random cliques wrt monotone circuits relate to density...
vzn
<cc.complexity-theory><ds.algorithms><complexity-classes><np-complete>
"Almost easy" NP-complete problems
Andras Farago
# "Almost easy" NP-complete problems

(Asked by: username_0 on 2015-11-15)

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?

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, np-complete
> **Comments:**
> **username_1**: 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.  
> **username_2**: FYI: Your choice of nomenclature, while natural, conflicts with some existing nomenclature: The class [Almost-P](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:A#almostp) 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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pclose). Given the defn of P-close, maybe a good name for your concept is P-density-close, or P-close-enough :).  
> **username_0**: @JoshuaGrochow Thank you, I edited the question, using one of your recommended names, to avoid conflicting with existing terminology.  
> **username_3**: 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?  
> **username_1**: It seems that the right formalism of your intuition is the notion of [Generic-case complexity] (http://www.wikipedia.org/wiki/Generic-case_complexity).  
> **username_0**: @AndrásSalamon One can construct NP-complete languages with non-vanishing density. For example, let $L$ contain those graphs that have a half-clique (a clique on $\geq n/2$ vertices) **or** have an odd number of edges. This contains more than half of all $n$-vertex graphs, yet it remains  hard, because to decide membership in $L$, we have to be able to decide half-clique on graphs with an even number of edges, which is still hard. On the other hand, $L$ is solvable in polynomial time on almost all inputs (just return the parity of the number of edges).  
> **username_3**: @AndrasFarago how are you encoding graphs with alphabet $\{0,1\}$?  
> **username_0**: @AndrásSalamon Let us use labeled graphs. Then each $(n^2-n)/2$ long binary string uniquely encodes  the upper half of the adjacency matrix of an $n$-vertex labeled graph, and so the graph itself.  
> **username_0**: @MohammadAl-Turkistany You may be right, I am not familiar with generic case complexity. But it still appears different, as they say: "An algorithm is in GenP (generically polynomial time) if it never gives incorrect answers and if it gives correct answers in polynomial time on a generic set of inputs." This seems different from what I asked for, since I do allow that the algorithm gives incorrect answer, just "rarely." But it is conceivable that the two concepts may be equivalent.  
> **username_3**: @AndrasFarago OK, but isn't your half-clique/odd-edges example rather unnatural?  The only reason its density doesn't vanish is because an easy language has been adjoined to bolster it.  I'm still trying to find a natural language that is hard and does not have vanishing density.  This seems to be the core of your question, even if one restricts attention to the ratio of yes-instances to valid inputs.  
> **username_0**: @AndrásSalamon I agree that artificially adjoining an easy set, just to beef up the density, may be viewed as unnatural. But even if a truly natural    NP-complete language is exhibited with a non-vanishing set of                      yes-instances, it may still be hard to prove that there is no way to shave off an easy set from it, such that the remaining yes-instances already constitute a vanishing set.  
> **username_3**: @AndrasFarago Agreed that it is not enough.  However, bounded treewidth and other natural restrictions of graphs to ensure polynomial-time algorithms yield nowhere dense classes.  These seem to have vanishing density in the sense used here, even though they have superpolynomial density.  So to me the first key part of your question seems to be whether there are actually any natural, hard languages that have non-vanishing density.  (Also, the usual meaning of "dense" is $2^{n^\varepsilon}$ in the size-$n$ instances, for some $\varepsilon > 0$, so perhaps this is a kind of "linear density".)  
> **username_4**: all this reminds me; it would be nice if someone did a survey in this area & covered (1) mahaneys theorem (2) (NP complete) slice functions for monotone circuits (3) hartmanis-stearns isomorphism conjecture. these seem to be the main areas in the literature that attack P vs NP from the angle of "density". (oh yeah, natural proofs also.) they all seem to be connected but there is little tieing it all together... think all relate to your question but the details would be subtle to elaborate/ articulate... also rossmans results on random cliques wrt monotone circuits relate to density...  

---

## 1 answers

### Answer by username_0 on 2015-11-18. Score: 5

I looked into whether there is a generally accepted hypothesis in complexity theory, which implies that there must exist an **NP**-complete language that cannot be accepted in polynomial time on almost all inputs (as defined in the question).

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](https://en.wikipedia.org/wiki/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](http://web.cs.iastate.edu/~lutz/=PAPERS/tprbm-eatcs.pdf). 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.

However, it still remains unclear whether an example exists that represents a *natural* problem.

> **Comments:**
> **username_2**: Bi-immunity is also *much* stronger than your condition, and is related to the more common usage of "almost all" in structural complexity theory, namely "for all but finitely many"...  
> **username_0**: @JoshuaGrochow I agree, but it appears that, in a sense, P-bi-immunity means   _too strong_  intractability. It does not seem to occur among natural NP-complete problems. It is surprising to me that apparently there is no result that provides conditions merely for the existence of a "weakly almost everywhere" intractable NP-complete language. By "weakly almost everywhere" I mean that the "all but finitely many" condition is replaced by "all but vanishingly many." That might relate  better to what is really encountered in practice.  
> **username_0**: @RickyDemer As far as I know, it is not known whether NP is                          p-measurable.  

---

