21
$\begingroup$

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?

Improve this question
$\endgroup$
15
  • 3
    $\begingroup$ 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. ​ ​ $\endgroup$
    – user6973
    Nov 15, 2015 at 6:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mohammad Al-Turkistany
    Nov 15, 2015 at 12:29
  • 8
    $\begingroup$ 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 :). $\endgroup$
    – Joshua Grochow
    Nov 15, 2015 at 14:26
  • 1
    $\begingroup$ On the other hand, the "Graph Coloration" decision problem is presumably a candidate for such a problem. $\;$ $\endgroup$
    – user6973
    Nov 15, 2015 at 19:02
  • 5
    $\begingroup$ 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? $\endgroup$
    – András Salamon
    Nov 16, 2015 at 12:02

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ 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"... $\endgroup$
    – Joshua Grochow
    Nov 18, 2015 at 5:07
  • 1
    $\begingroup$ @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. $\endgroup$
    – Andras Farago
    Nov 18, 2015 at 13:22
  • $\begingroup$ Is NP known to be p-measurable? ​ ​ $\endgroup$
    – user6973
    Dec 10, 2015 at 20:45
  • $\begingroup$ @RickyDemer As far as I know, it is not known whether NP is p-measurable. $\endgroup$
    – Andras Farago
    Dec 11, 2015 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.