21

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?

Andras Farago
  • 11,396
  • 37
  • 70
  • 3
    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. ​ ​ –  Nov 15 '15 at 06:26
  • 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. – Mohammad Al-Turkistany Nov 15 '15 at 12:29
  • 8
    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
  • @JoshuaGrochow Thank you, I edited the question, using one of your recommended names, to avoid conflicting with existing terminology. – Andras Farago Nov 15 '15 at 14:43
  • 1
    On the other hand, the "Graph Coloration" decision problem is presumably a candidate for such a problem. $;$ –  Nov 15 '15 at 19:02
  • 5
    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
  • 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 Nov 16 '15 at 21:50
  • @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 Nov 17 '15 at 04:16
  • @AndrasFarago how are you encoding graphs with alphabet ${0,1}$? – András Salamon Nov 17 '15 at 04:20
  • @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 Nov 17 '15 at 04:38
  • @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 Nov 17 '15 at 04:46
  • @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 Nov 17 '15 at 06:20
  • @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 Nov 17 '15 at 13:52
  • 1
    @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 Nov 17 '15 at 16:20
  • 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 Nov 17 '15 at 16:53

1 Answers1

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 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.

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

Andras Farago
  • 11,396
  • 37
  • 70
  • 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"... – Joshua Grochow Nov 18 '15 at 05:07
  • 1
    @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 Nov 18 '15 at 13:22
  • Is NP known to be p-measurable? ​ ​ –  Dec 10 '15 at 20:45
  • @RickyDemer As far as I know, it is not known whether NP is p-measurable. – Andras Farago Dec 11 '15 at 21:26