<p>As others have pointed out, it's debatable to what extent the thing you're trying to explain is even true.  One could argue that, in the 60s and 70s, theoretical computer scientists were just more <i>interested</i> in the sorts of problems that turn out to be either in P or else NP-complete.  Today, because of the rise of complexity-theoretic cryptography, quantum computing, lattices, etc.---as well as the simple fact that NP-completeness has become so well-understood---we've become more and more interested in the sorts of problems that turn out to be NP-intermediate.</p>

<p>Still, one could ask: to the extent that the thing is true---that is, to the extent that so many natural search and optimization problems "snap" to being either NP-complete or else in P---to that extent, <i>why</i> is it true?  Here, I think you can get a lot of intuition by looking at an earlier phenomenon from computability: that so many natural models of computation "snap" to being Turing-complete.  In that case, I'd say the explanation is that, once you have a few basic components---a read/write memory, loops, conditionals, etc.---it's hard to <i>avoid</i> being able to simulate a Turing machine, and therefore being Turing-complete.  In much the same way, once your search or optimization problem has a few basic components---most importantly, the ability to construct "gadgets" that mimic logic gates like AND, OR, and NOT---it's hard to avoid being able to encode SAT and therefore being NP-complete.</p>

<p>The way I like to think about it, problems like SAT exert a powerful "gravitational pull" on all the other computational problems in their vicinity, making them want to "snap up" to being NP-complete also.  So, it normally doesn't even require special explanation when yet another problem succumbs to that pull!  What's more striking, and more in need of explanation, is when an (apparently) hard NP problem has some property that lets it <i>resist</i> the gravitational pull of SAT.  We then want to know: what <i>is</i> that property?  <i>Why</i> can't you play the usual NP-completeness trick for this problem, of constructing gadgets that encode Boolean logic gates?  I made up a list of some common answers to that question in <a href="https://cstheory.stackexchange.com/questions/20883/techniques-for-showing-that-problem-is-in-hardness-limbo">this recent CS.SE answer</a>, but (as another commenter already pointed out) there are other possible answers that I missed.</p>

CC BY-SA 3.0
2014-02-10T16:13:42.367Z
Also relevant for the last part is Scott's question http://cstheory.stackexchange.com/questions/19256/overarching-reasons-why-problems-are-in-p-or-bpp
András Salamon
CC BY-SA 3.0
2014-02-08T16:00:00.770Z
2014-02-08T16:00:00.770Z
2017-04-13T12:32:28.077Z
Scott Aaronson
<p>Many natural problems can be expressed as Constraint Satisfaction Problems, and there are dichotomy theorems for CSPs.</p>

CC BY-SA 3.0
2014-02-08T01:41:25.673Z
2014-02-08T01:41:25.673Z
Joshua Grochow
<p>Just a joke: after thinking about the "SAT gravitational pull" in the Scott Aaronson's nice answer, another metaphore came to my mind: the <em>3-SAT 2-SAT sandwich</em> !</p>

<p><img src="https://i.sstatic.net/TDApg.png" alt="enter image description here"></p>

<p><br><br>
... but I don't know if the sandwich can be filled with natural ingredients (however I found that it could be filled with some $(2 + \frac{(\log n)^k}{n^2})$-SAT sauce [1] if the Exponential-Time Hypothesis is true) :-D </p>

<p>Another result in [1] is that it cannot be filled with $(2+1/n^{2−\epsilon}),0&lt;\epsilon&lt;2$ .</p>

<p>[1] <a href="http://www.sciencedirect.com/science/article/pii/S0166218X0300194X" rel="noreferrer">Yunlei Zhao, Xiaotie Deng, C.H Lee, Hong Zhu, $(2+f(n))$-SAT and its properties</a>, Discrete Applied Mathematics, Volume 136, Issue 1, 30 January 2004, Pages 3-11, ISSN 0166-218X.</p>

CC BY-SA 3.0
2014-03-14T02:48:21.380Z
@MarzioDeBiasi you should consider adding those two references directly to your answer (where they are searchable) instead of hiding them in the comments.
Artem Kaznatcheev
CC BY-SA 3.0
2014-02-11T00:26:13.433Z
However, it cannot be filled with $(2+\varepsilon)$-SAT: http://eccc.hpi-web.de/report/2013/159/
Joshua Grochow
CC BY-SA 3.0
2014-02-11T07:36:00.170Z
@JoshuaGrochow: my reference for the "sauce" is the [Zhao, Deng, Lee and Zhu paper](http://www.sciencedirect.com/science/article/pii/S0166218X0300194X) "$(2+f(n))$-SAT and it properties"   they also proved that it cannot be filled with $(2+1/n^{2-\epsilon}), 0<\epsilon<2$ ... I'll give a look to the $(2+\epsilon)$-SAT paper (I only opened it and it is strange that they didn't put Zhao et al. work in their references)
Marzio De Biasi
CC BY-SA 3.0
2014-02-11T14:55:11.627Z
The definitions of $(2+f(n))$-SAT in the two papers are different; I think both are correct!
Joshua Grochow
CC BY-SA 3.0
2014-02-10T00:12:56.530Z
2014-03-14T10:09:27.397Z
2014-03-14T10:09:27.397Z
Marzio De Biasi
<p>We can not rule-out a forth possibility that there are plenty of <strong>natural</strong> $NP$-intermediate problems. The apparent scarcity is due to lack of necessary techniques and tools required to prove $NP$-intermediate status under some plausible complexity conjecture (Arora and Barak noted that we can not prove the $NP$-intermediate status of any natural $NP$ problem even assuming $P \ne NP$). </p>

<p>It seems that the floodgates of natural $NP$-intermediate problems are open. <a href="http://www.ida.liu.se/~vicla67/cp2013.pdf">Jonsson, Lagerkvist, and Nordh</a> extended the diagonalization technique of Ladner, known as <em>blowing holes in problems</em>, and applied it to Constraint Satisfaction Problems. They obtained a CSP that is a candidate for $NP$-intermediate status. They proved that propositional abduction problem has $NP$-intermediate fragments.</p>

<p>Also, <a href="http://dl.acm.org/citation.cfm?id=1206036">Grohe</a> proved the existence of $NP$-intermediate CSP problems assuming that $FPT \ne W[1]$. He obtained such problems by restricting the tree-width of the corresponding primal graphs.</p>

<p><strong>References</strong>:  </p>

<p>1- M. Grohe. The complexity of homomorphism and constraint satisfaction problems
seen from the other side. Journal of the ACM, 54(1), article 1, 2007</p>

<p>2- Peter Jonsson, Victor Lagerkvist and Gustav Nordh. Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction. In Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP-2013). 2013.</p>

CC BY-SA 3.0
2014-02-08T15:11:59.337Z
why do these CSP problems not fall under the dichotomy conjecture?
Sasho Nikolov
CC BY-SA 3.0
2014-02-08T15:15:41.340Z
Is restricting the treewidth as in Grohe's result actually natural? (The question is not rhetorical - I honestly don't know.) In my opinion, the Johnsson-Lagerkvsit-Nordh constructions only seem *slightly* more natural than Ladner's. I think the point in your first paragraph is an excellent one.
Joshua Grochow
CC BY-SA 3.0
2014-02-08T15:32:02.320Z
@JoshuaGrochow I'am afraid that it is arguable as there is no formal notion for what **natural** means.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-08T15:34:10.890Z
@SashoNikolov Do you mean the dichotomy conjecture of Feder and Vardi?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-08T15:38:40.287Z
@MohammadAl-Turkistany yes
Sasho Nikolov
CC BY-SA 3.0
2014-02-08T16:12:57.243Z
@SashoNikolov My understanding is that the properties stated in Theorem 3 in the second reference exclude such CSPs.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-08T16:16:17.680Z
The Feder-Vardi dichotomy applies to problems CSP(_,$B$) consisting of all pairs $(S,T)$ of relational structures with $S$ arbitrary and $T \in B$.  It says nothing about other classes of CSP instances, such as CSP($A$,$B$) for restricted classes $A$ and $B$.
András Salamon
CC BY-SA 3.0
2014-02-08T16:20:34.300Z
@AndrásSalamon So, Do you think that the $NP$-intermediate CSP of Johnsson-Lagerkvsit-Nordh contradicts the Feder-Vardi dichotomy conjecture?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-08T16:58:20.417Z
@MohammadAl-Turkistany: I know there is no formal notion of natural. I was asking whether, relative to ideas that are frequently studied in FPT, or in the opinion of people who study FPT, restricting treewidth in the way Grohe does would commonly be seen as natural.
Joshua Grochow
CC BY-SA 3.0
2014-02-08T17:07:49.633Z
@AndrásSalamon Understood, thanks! (Mohammad: Andras is saying that the way Grohe constrains CSP instances, Feder-Vardi does not imply anything; comparing the Hell-Nesetril theorem with Grohe's result clarified this point for me.)
Sasho Nikolov
CC BY-SA 3.0
2014-02-08T17:30:10.837Z
@JoshuaGrochow Yes. It is considered "natural".
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-10T09:54:04.010Z
@MohammadAl-Turkistany: I don't see a contradiction.  JLN explicitly construct classes of instances that are not in the form CSP($A$,$\_$) or CSP($\_$,$B$), so they avoid the dichotomies that are known.  See also the earlier pair of papers by Chen-Thurley-Weyer and Bodirsky-Grohe for similar ideas.
András Salamon
CC BY-SA 3.0
2014-02-08T13:24:29.160Z
2014-02-08T13:35:02.180Z
2014-02-08T13:35:02.180Z
Mohammad Al-Turkistany
<p>Here is a fairy tale about the Goldilocks structure of NP-intermediate
problems.  (Warning: this story may be a useful fallacy to generate
and test potential hypotheses, but is not meant to be scientifically
rigorous.  It relies on one part Exponential Time Hypothesis, a dash
of Kolmogorov complexity magic, some pieces borrowed from the theory
of SAT solving, and Terence Tao's heuristic trichotomy for problems.
Consume at own risk, as with all hand-waving concoctions about
mathematics.)</p>

<p>If nearly all instances in a problem in NP are highly structured,
then the problem is actually in P.  The instances thus nearly all
contain a lot of redundancy, and a polynomial-time algorithm for the
problem is a way to factor out the redundancy.  It is even conceivable
that every problem in P can be obtained by taking some problem in EXP
and adding some structured redundancy, via some form of padding (not
necessarily the usual kind).  If this were so, then a polynomial-time
algorithm could be seen as an efficient way to undo that padding.</p>

<p>If there are enough instances that are not structured, forming a
"core of hardness", then the problem is NP-complete.</p>

<p>However, if this "core of hardness" is too sparse, then it only
has room to represent some of SAT, so the problem is in P or
NP-intermediate.  (This argument is the essence of Ladner's theorem).
To use Scott's analogy, the "core of hardness" exerts a gravitational
pull on the problem, toward it being NP-complete.  The instances in
the "core of hardness" do not contain much redundancy, and the only
realistic algorithm that works for all those instances is brute force
search (of course, if there are only finitely many, then table lookup
works, too).</p>

<p>From this perspective, NP-intermediate problems should be rare
in practice, since they require a fine Goldilocks balance between
instances that are structured and unstructured.  Instances should have
enough redundancy that they are partially amenable to an algorithm,
but there should be enough of a core of hardness that the problem is
not in P.</p>

<hr>

<p>One can tell an even simpler (and amusing, but also potentially even
more misleading) story based on puzzles.  With just a few constraints,
one can force a lot of search to be done, for instance NxN Sudoku
is NP-complete.  Now consider being asked to solve lots of small
puzzles as a single instance, in one go (e.g. many 9x9 Sudokus).
The time taken is going to be roughly linear in the number of puzzles
in each instance, and this problem is then in P.  For intermediate
problems, one can think of each instance being a largish (but not
too large) number of Sudokus on largish (but not too large) grids.
The reason we don't observe many such problems is because they would be
dreary to pose and to solve!</p>

CC BY-SA 3.0
2014-02-11T00:24:56.693Z
Here is some further technical meat to add to your "core of hardness" story. N. Lynch (1975) defined a p-complexity core for a language $L$ to be a set of strings $C$ such that for all algorithms that correctly decide $L$ on all inputs, for all $k$, the algorithm runs in time $n^k + k$ on only finitely many inputs from $C$. Lynch showed that every $L \notin \mathsf{P}$ has a p-complexity core, and Orponen and Schoning showed that every such $L$ has a core that is not polynomially sparse. One might (*might*) hypothesize that languages in NP with sufficiently dense cores have to be NP-complete.
Joshua Grochow
CC BY-SA 3.0
2014-02-11T22:33:15.130Z
The references Joshua mentioned: Lynch: http://dx.doi.org/10.1145/321892.321895 and Orponen-Schöning: http://dx.doi.org/10.1016/S0019-9958(86)80024-9 also see Orponen-Ko-Schöning-Watanabe: http://dx.doi.org/10.1145/174644.174648
András Salamon
CC BY-SA 3.0
2014-02-10T09:47:30.477Z
2014-02-10T09:47:30.477Z
András Salamon
<p>Several answers pointed out that the premise of my question (the relative scarcity of natural $\mathsf{NPI}$-candidates) might be questionable. After some thinking, I must accept that they indeed have a point. In fact, one can even go as far as to make the case that there are actually <em> more </em> natural $\mathsf{NPI}$ candidates than natural $\mathsf{NP}$-complete problems.  The argument could go as follows.</p>

<p>Consider the LOGCLIQUE problem, which aims at deciding whether an $n$-vertex input graph has a clique of size $\geq \log n$. This is a natural $\mathsf{NPI}$ candidate. Now, the same type of "scaling down" can be carried out on <em> any </em> $\mathsf{NP}$-complete problem. Simply replace the question "does the input string $x$ have a property $Q$?" by the  scaled down question "does $x$ have a logarithmically  sized substring that has property $Q$?" (We may restrict ourselves only to those substrings that represent the appropriate type of structure, such as subgraphs etc.) 
Arguably, if the original problem was natural, the scaling down does not change this, since we only alter the size of what is sought for. The resulting problem will be an $\mathsf{NPI}$ candidate, since it is solvable in quasi-polynomial time, but still unlikely to fall into $\mathsf{P}$, as the mere size restriction probably does not introduce new structure.</p>

<p>This way, we can construct a natural $\mathsf{NPI}$ candidate for <em> every </em> natural $\mathsf{NP}$-complete problem. Additionally, there are also generic candidates that do not arise via scaling down, such as Graph Isomorphism, Factoring etc. Thus, one can indeed make the case that "natural-$\mathsf{NPI}$" is actually more populous than "natural $\mathsf{NPC}$."</p>

<p>Of course, this scaling down process, using Scott's nice metaphor, gives an obvious reason for resisting the "gravitational pull" of SAT. While there are papers published about LOGCLIQUE and similar problems, they did not draw too much attention, as these problems are less exciting than the the generic  $\mathsf{NPI}$ candidates, where there is no clear understanding of how the gravitational pull is resisted, without falling into $\mathsf{P}$.</p>

CC BY-SA 3.0
2014-02-12T11:51:48.860Z
Your statement "we can construct a natural NPI candidate for every natural NP-complete problem" seems to be too strong.  Characterizing a _subclass of NP_ for which we can do this seems worthwhile, via a formalisation of your "scaling down" argument, but I'm not yet convinced that the argument applies to all of NP.
András Salamon
CC BY-SA 3.0
2014-02-12T16:45:53.437Z
I think, it can be applied to all of NP in the following way. $Every$    problem in NP is presentable in the following format: given an input string $x$, does there exist another string $y$, such that $|y|\leq p(|x|)$, and $(x,y)\in L$, where $L$ is a polynomial-time decidable language, and $p$ is a polynomial. Now, the scaled down version is this:  does there exist a substring $x'$ of $x$, such that $|x'|\geq \log |x|$, and there exist another string $y'$ with $|y'|\leq p(|x'|)$ and $(x',y')\in L$.
Andras Farago
CC BY-SA 3.0
2014-02-10T20:38:35.693Z
Your argument seems fine for problems in $W[1]$, but it seems to fail higher up in the W-hierarchy.  Yet you contend that this works for "_every_ natural NP-complete problem".  What am I missing?
András Salamon
CC BY-SA 3.0
2014-02-10T22:32:08.220Z
My understanding is that the scaling down can be done independently from any parametrization. If the original problem asks  "does the input string $x$ have a property $Q$?" then you can always replace it by the question "does $x$ have a $O(\log |x|)$ sized substring that has property Q?" I do not see the relationship with parametrized complexity.
Andras Farago
CC BY-SA 3.0
2014-02-10T23:38:09.567Z
For 3-COLOURING, what is the scaled down version of the problem?
András Salamon
CC BY-SA 3.0
2014-02-10T23:51:12.727Z
For 3-COLORING the scaled down version is this: does the $n$-vertex input graph contain a 3-colorable subgraph with at least $\log n$ vertices?
Andras Farago
CC BY-SA 3.0
2014-02-11T00:03:33.167Z
I understand that the scaling down works for any problem, but I would argue that it's only *natural* for problems that are (naturally) parametrized to begin with. Viz: LOGCLIQUE is fairly natural, but "Does a graph on $n$ vertices have a $\log n$-sized subgraph that is 3-colorable?" doesn't seem natural to me, because the original problem had nothing to do with finding a widget (e.g. clique) of a certain size.
Joshua Grochow
CC BY-SA 3.0
2014-02-11T00:22:03.137Z
"Naturalness" is indeed a rather elusive concept. Nevertheless, I do not see why the property "being a clique" is more natural than "being 3-colorable."  Once we accept that these are equally natural properties, then looking for a $\log n$-vertex subgraph with the property appears (to me) equally natural for both properties.
Andras Farago
CC BY-SA 3.0
2014-02-11T00:28:13.360Z
It's not the difference b/w "being a clique" and "being 3-colorable". It's the difference between the original problem being: 1) does a graph have a subgraph with some property of a given size (e.g. CLIQUE) vs. 2) does a graph have a property. In the case of (1), changing the size to be log is natural, b/c the *size* of the subgraph was already part of the question. When you do your trick to (2), you *add in* the size of the subgraph as a new part of the problem.
Joshua Grochow
CC BY-SA 3.0
2014-02-11T00:34:35.080Z
We may state 3-colorability this way: does the graph have 3 disjoint independent sets, such that the sum of their sizes is at least $k$?  Then with $k=n$ we get the original problem, with $k=\log n$ we get the scaled down version.
Andras Farago
CC BY-SA 3.0
2014-02-11T00:47:17.850Z
Interesting! I hadn't thought of that. Given the plethora of NP-complete problems, I'd still think there are many that cannot be phrased with such a natural parameter (even though your trick works regardless).
Joshua Grochow
CC BY-SA 3.0
2014-02-11T01:07:00.513Z
Technically, all graph problems where we want to decide whether the input graph has a property $Q$, can be phrased this way: does the graph have a subgraph on $\geq k$ vertices with property $Q$? Then with $k=n$ we get the original problem, with $k=\log n$ the scaled down version. Once the property $Q$ is accepted as natural, there seems to be no reason to view it "more natural" for certain values of $k$, than for others. Then from here it is only one step to apply this for general input strings, rather than graphs, so that we may include any NP-complete problem.
Andras Farago
CC BY-SA 3.0
2014-02-11T18:32:56.267Z
I'm provisionally prepared to accept that this works for constraint satisfaction problems (which cover most graph problems in NP), since one can always weaken the problem by asking for a partial homomorphism of logarithmic size instead of a homomorphism.  (In other words, every CSP has a natural weakening in this way.)  However, what about problems in NP that are not known to be naturally expressible as CSPs, such as Partition, Integer Linear Programming, Factoring, or Regular Grammar Inequivalence?
András Salamon
CC BY-SA 3.0
2014-02-11T20:58:47.543Z
Let us take the Partition problem, as an example. Here the input is a set $S$ of  numbers, and the question is whether there is a subset $A$, such that the sum of numbers in $A$ is the same as in $S-A$. The scaled down version would be this: let $n=|S|$; is there a $\geq \log n$-sized subset $S'$ of $S$, such that there is a solution to Partition on $S'$?
Andras Farago
CC BY-SA 3.0
2014-02-11T23:22:39.033Z
OK, and moreover ILP is a CSP with an infinite domain.  That leaves Factoring and Regular Grammar Inequivalence.  For problems like these, I don't see what a natural "subproblem" would be, so how does your scaling argument work in those cases?
András Salamon
CC BY-SA 3.0
2014-02-10T19:02:23.533Z
2014-02-10T19:02:23.533Z
Andras Farago
<p>It is well known by Ladner's Theorem that if ${\mathsf P}\neq \mathsf {NP}$, then there exist infinitely many $\mathsf {NP}$-intermediate ($\mathsf{NPI}$) problems. There are also natural candidates for this status, such as Graph Isomorphism, and a number of others, see 
<a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc">Problems Between P and NPC</a>. Nevertheless, the vast majority in the crowd of known $natural$ $\mathsf {NP}$-problems are known to be either in $\mathsf {P}$ or $\mathsf {NPC}$. Only a small fraction of them remains a candidate for $\mathsf {NPI}$. In other words, if we randomly pick a natural $\mathsf {NP}$-problem among the known ones, we have very little chance to pick an $\mathsf {NPI}$ candidate. Is there any explanation for this phenomenon? </p>

<p>I could think up 3 possible explanations, more on the philosophical side:</p>

<ol>
<li><p>The reason for having such a small fraction of natural $\mathsf {NPI}$ candidates is that     $\mathsf {NPI}$ will eventually turn out to be empty. I know, this implies ${\mathsf P} =\mathsf {NP}$, so it is very unlikely. Nevertheless, one could still argue (though I'm not one of them) that the rareness of natural $\mathsf {NPI}$ problems is  an empirical observation that appears to actually support ${\mathsf P} =\mathsf {NP}$, in contrast to most other observations. </p></li>
<li><p>The smallness of "natural-$\mathsf {NPI}$" represents a kind of sharp phase transition between easy and hard problems. Apparently,  the meaningful, natural algorithmic problems behave in a way that they tend to be either easy or hard, the transition is narrow (but still exists).</p></li>
<li><p>The argument in 2 can be taken to the extreme: eventually all problems in "natural-$\mathsf {NPI}$" will be put into $\mathsf {P} \cup \mathsf {NPC}$, yet ${\mathsf P}\neq \mathsf {NP}$, so $\mathsf {NPI}\neq \emptyset$. This would mean that all remaining problems in $\mathsf {NPI}$ are "unnatural" (contrived, without real-life meaning). An interpretation of this could be that natural problems are either easy or hard; the transition is only a logical construct, without "physical" meaning. This is somewhat reminiscent to the case of irrational numbers, which are perfectly logical, but do not arise as the measured value of any  physical quantity. As such, they do not come from physical reality, they are rather in the "logical closure" of that reality.</p></li>
</ol>

<p>Which explanation do you like the best, or can you suggest another one?</p>

CC BY-SA 3.0
2014-02-08T01:36:29.330Z
Um, the length of the diagonal of a 1cm x 1cm square is an irrational number...
Joshua Grochow
CC BY-SA 3.0
2014-02-08T01:42:25.443Z
You might also find it interesting that in the theory of resource-bounded measure, the collection of NP-complete sets has p-measure 0. In other words, p-random sets in NP are not NP-complete. Indeed, this is true of any single polynomial-time many-one degree. (The measure of the collection of all NP sets is an open question: if it is nonzero, or not measurable, then $\mathsf{P} \neq \mathsf{NP}$.)
Joshua Grochow
CC BY-SA 3.0
2014-02-08T02:30:21.383Z
the answer has mostly to do with what problems we find "natural" which is a rather philosophical question. also it's not quite clear that the premise of the question holds: many problems arising from cryptography have intermediate complexity. finally, what you are saying about irrational numbers is absurd.
Sasho Nikolov
<cc.complexity-theory><p-vs-np><np-intermediate>
Why are so few natural candidates for NP-intermediate status?
Andras Farago
# Why are so few natural candidates for NP-intermediate status?

(Asked by: username_0 on 2014-02-07)

It is well known by Ladner's Theorem that if ${\mathsf P}\neq \mathsf {NP}$, then there exist infinitely many $\mathsf {NP}$-intermediate ($\mathsf{NPI}$) problems. There are also natural candidates for this status, such as Graph Isomorphism, and a number of others, see
[Problems Between P and NPC](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc). Nevertheless, the vast majority in the crowd of known $natural$ $\mathsf {NP}$-problems are known to be either in $\mathsf {P}$ or $\mathsf {NPC}$. Only a small fraction of them remains a candidate for $\mathsf {NPI}$. In other words, if we randomly pick a natural $\mathsf {NP}$-problem among the known ones, we have very little chance to pick an $\mathsf {NPI}$ candidate. Is there any explanation for this phenomenon?

I could think up 3 possible explanations, more on the philosophical side:

1. The reason for having such a small fraction of natural $\mathsf {NPI}$ candidates is that $\mathsf {NPI}$ will eventually turn out to be empty. I know, this implies ${\mathsf P} =\mathsf {NP}$, so it is very unlikely. Nevertheless, one could still argue (though I'm not one of them) that the rareness of natural $\mathsf {NPI}$ problems is an empirical observation that appears to actually support ${\mathsf P} =\mathsf {NP}$, in contrast to most other observations.
2. The smallness of "natural-$\mathsf {NPI}$" represents a kind of sharp phase transition between easy and hard problems. Apparently, the meaningful, natural algorithmic problems behave in a way that they tend to be either easy or hard, the transition is narrow (but still exists).
3. The argument in 2 can be taken to the extreme: eventually all problems in "natural-$\mathsf {NPI}$" will be put into $\mathsf {P} \cup \mathsf {NPC}$, yet ${\mathsf P}\neq \mathsf {NP}$, so $\mathsf {NPI}\neq \emptyset$. This would mean that all remaining problems in $\mathsf {NPI}$ are "unnatural" (contrived, without real-life meaning). An interpretation of this could be that natural problems are either easy or hard; the transition is only a logical construct, without "physical" meaning. This is somewhat reminiscent to the case of irrational numbers, which are perfectly logical, but do not arise as the measured value of any physical quantity. As such, they do not come from physical reality, they are rather in the "logical closure" of that reality.

Which explanation do you like the best, or can you suggest another one?

**Tags:** cc.complexity-theory, p-vs-np, np-intermediate
> **Comments:**
> **username_1**: Um, the length of the diagonal of a 1cm x 1cm square is an irrational number...  
> **username_1**: You might also find it interesting that in the theory of resource-bounded measure, the collection of NP-complete sets has p-measure 0. In other words, p-random sets in NP are not NP-complete. Indeed, this is true of any single polynomial-time many-one degree. (The measure of the collection of all NP sets is an open question: if it is nonzero, or not measurable, then $\mathsf{P} \neq \mathsf{NP}$.)  
> **username_2**: the answer has mostly to do with what problems we find "natural" which is a rather philosophical question. also it's not quite clear that the premise of the question holds: many problems arising from cryptography have intermediate complexity. finally, what you are saying about irrational numbers is absurd.  

---

## 6 answers

### Answer by username_3 on 2014-02-08. Score: 29

As others have pointed out, it's debatable to what extent the thing you're trying to explain is even true. One could argue that, in the 60s and 70s, theoretical computer scientists were just more *interested* in the sorts of problems that turn out to be either in P or else NP-complete. Today, because of the rise of complexity-theoretic cryptography, quantum computing, lattices, etc.---as well as the simple fact that NP-completeness has become so well-understood---we've become more and more interested in the sorts of problems that turn out to be NP-intermediate.

Still, one could ask: to the extent that the thing is true---that is, to the extent that so many natural search and optimization problems "snap" to being either NP-complete or else in P---to that extent, *why* is it true? Here, I think you can get a lot of intuition by looking at an earlier phenomenon from computability: that so many natural models of computation "snap" to being Turing-complete. In that case, I'd say the explanation is that, once you have a few basic components---a read/write memory, loops, conditionals, etc.---it's hard to *avoid* being able to simulate a Turing machine, and therefore being Turing-complete. In much the same way, once your search or optimization problem has a few basic components---most importantly, the ability to construct "gadgets" that mimic logic gates like AND, OR, and NOT---it's hard to avoid being able to encode SAT and therefore being NP-complete.

The way I like to think about it, problems like SAT exert a powerful "gravitational pull" on all the other computational problems in their vicinity, making them want to "snap up" to being NP-complete also. So, it normally doesn't even require special explanation when yet another problem succumbs to that pull! What's more striking, and more in need of explanation, is when an (apparently) hard NP problem has some property that lets it *resist* the gravitational pull of SAT. We then want to know: what *is* that property? *Why* can't you play the usual NP-completeness trick for this problem, of constructing gadgets that encode Boolean logic gates? I made up a list of some common answers to that question in [this recent CS.SE answer](https://cstheory.stackexchange.com/questions/20883/techniques-for-showing-that-problem-is-in-hardness-limbo), but (as another commenter already pointed out) there are other possible answers that I missed.

> **Comments:**
> **username_4**: Also relevant for the last part is Scott's question http://cstheory.stackexchange.com/questions/19256/overarching-reasons-why-problems-are-in-p-or-bpp  

---

### Answer by username_1 on 2014-02-08. Score: 20

Many natural problems can be expressed as Constraint Satisfaction Problems, and there are dichotomy theorems for CSPs.


---

### Answer by username_5 on 2014-02-10. Score: 11

Just a joke: after thinking about the "SAT gravitational pull" in the Scott Aaronson's nice answer, another metaphore came to my mind: the *3-SAT 2-SAT sandwich* !

![enter image description here](https://i.sstatic.net/TDApg.png)

... but I don't know if the sandwich can be filled with natural ingredients (however I found that it could be filled with some $(2 + \frac{(\log n)^k}{n^2})$-SAT sauce [1] if the Exponential-Time Hypothesis is true) :-D

Another result in [1] is that it cannot be filled with $(2+1/n^{2−\epsilon}),0<\epsilon<2$ .

[1] [Yunlei Zhao, Xiaotie Deng, C.H Lee, Hong Zhu, $(2+f(n))$-SAT and its properties](http://www.sciencedirect.com/science/article/pii/S0166218X0300194X), Discrete Applied Mathematics, Volume 136, Issue 1, 30 January 2004, Pages 3-11, ISSN 0166-218X.

> **Comments:**
> **username_1**: However, it cannot be filled with $(2+\varepsilon)$-SAT: http://eccc.hpi-web.de/report/2013/159/  
> **username_5**: @JoshuaGrochow: my reference for the "sauce" is the [Zhao, Deng, Lee and Zhu paper](http://www.sciencedirect.com/science/article/pii/S0166218X0300194X) "$(2+f(n))$-SAT and it properties"   they also proved that it cannot be filled with $(2+1/n^{2-\epsilon}), 0<\epsilon<2$ ... I'll give a look to the $(2+\epsilon)$-SAT paper (I only opened it and it is strange that they didn't put Zhao et al. work in their references)  
> **username_1**: The definitions of $(2+f(n))$-SAT in the two papers are different; I think both are correct!  
> **username_6**: @MarzioDeBiasi you should consider adding those two references directly to your answer (where they are searchable) instead of hiding them in the comments.  

---

### Answer by username_7 on 2014-02-08. Score: 8

We can not rule-out a forth possibility that there are plenty of **natural** $NP$-intermediate problems. The apparent scarcity is due to lack of necessary techniques and tools required to prove $NP$-intermediate status under some plausible complexity conjecture (Arora and Barak noted that we can not prove the $NP$-intermediate status of any natural $NP$ problem even assuming $P \ne NP$).

It seems that the floodgates of natural $NP$-intermediate problems are open. [Jonsson, Lagerkvist, and Nordh](http://www.ida.liu.se/~vicla67/cp2013.pdf) extended the diagonalization technique of Ladner, known as *blowing holes in problems*, and applied it to Constraint Satisfaction Problems. They obtained a CSP that is a candidate for $NP$-intermediate status. They proved that propositional abduction problem has $NP$-intermediate fragments.

Also, [Grohe](http://dl.acm.org/citation.cfm?id=1206036) proved the existence of $NP$-intermediate CSP problems assuming that $FPT \ne W[1]$. He obtained such problems by restricting the tree-width of the corresponding primal graphs.

**References**:

1- M. Grohe. The complexity of homomorphism and constraint satisfaction problems
seen from the other side. Journal of the ACM, 54(1), article 1, 2007

2- Peter Jonsson, Victor Lagerkvist and Gustav Nordh. Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction. In Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP-2013). 2013.

> **Comments:**
> **username_2**: why do these CSP problems not fall under the dichotomy conjecture?  
> **username_1**: Is restricting the treewidth as in Grohe's result actually natural? (The question is not rhetorical - I honestly don't know.) In my opinion, the Johnsson-Lagerkvsit-Nordh constructions only seem *slightly* more natural than Ladner's. I think the point in your first paragraph is an excellent one.  
> **username_7**: @JoshuaGrochow I'am afraid that it is arguable as there is no formal notion for what **natural** means.  
> **username_7**: @SashoNikolov Do you mean the dichotomy conjecture of Feder and Vardi?  
> **username_2**: @MohammadAl-Turkistany yes  
> **username_7**: @SashoNikolov My understanding is that the properties stated in Theorem 3 in the second reference exclude such CSPs.  
> **username_4**: The Feder-Vardi dichotomy applies to problems CSP(_,$B$) consisting of all pairs $(S,T)$ of relational structures with $S$ arbitrary and $T \in B$.  It says nothing about other classes of CSP instances, such as CSP($A$,$B$) for restricted classes $A$ and $B$.  
> **username_7**: @AndrásSalamon So, Do you think that the $NP$-intermediate CSP of Johnsson-Lagerkvsit-Nordh contradicts the Feder-Vardi dichotomy conjecture?  
> **username_1**: @MohammadAl-Turkistany: I know there is no formal notion of natural. I was asking whether, relative to ideas that are frequently studied in FPT, or in the opinion of people who study FPT, restricting treewidth in the way Grohe does would commonly be seen as natural.  
> **username_2**: @AndrásSalamon Understood, thanks! (Mohammad: Andras is saying that the way Grohe constrains CSP instances, Feder-Vardi does not imply anything; comparing the Hell-Nesetril theorem with Grohe's result clarified this point for me.)  
> **username_7**: @JoshuaGrochow Yes. It is considered "natural".  
> **username_4**: @MohammadAl-Turkistany: I don't see a contradiction.  JLN explicitly construct classes of instances that are not in the form CSP($A$,$\_$) or CSP($\_$,$B$), so they avoid the dichotomies that are known.  See also the earlier pair of papers by Chen-Thurley-Weyer and Bodirsky-Grohe for similar ideas.  

---

### Answer by username_4 on 2014-02-10. Score: 7

Here is a fairy tale about the Goldilocks structure of NP-intermediate
problems. (Warning: this story may be a useful fallacy to generate
and test potential hypotheses, but is not meant to be scientifically
rigorous. It relies on one part Exponential Time Hypothesis, a dash
of Kolmogorov complexity magic, some pieces borrowed from the theory
of SAT solving, and Terence Tao's heuristic trichotomy for problems.
Consume at own risk, as with all hand-waving concoctions about
mathematics.)

If nearly all instances in a problem in NP are highly structured,
then the problem is actually in P. The instances thus nearly all
contain a lot of redundancy, and a polynomial-time algorithm for the
problem is a way to factor out the redundancy. It is even conceivable
that every problem in P can be obtained by taking some problem in EXP
and adding some structured redundancy, via some form of padding (not
necessarily the usual kind). If this were so, then a polynomial-time
algorithm could be seen as an efficient way to undo that padding.

If there are enough instances that are not structured, forming a
"core of hardness", then the problem is NP-complete.

However, if this "core of hardness" is too sparse, then it only
has room to represent some of SAT, so the problem is in P or
NP-intermediate. (This argument is the essence of Ladner's theorem).
To use Scott's analogy, the "core of hardness" exerts a gravitational
pull on the problem, toward it being NP-complete. The instances in
the "core of hardness" do not contain much redundancy, and the only
realistic algorithm that works for all those instances is brute force
search (of course, if there are only finitely many, then table lookup
works, too).

From this perspective, NP-intermediate problems should be rare
in practice, since they require a fine Goldilocks balance between
instances that are structured and unstructured. Instances should have
enough redundancy that they are partially amenable to an algorithm,
but there should be enough of a core of hardness that the problem is
not in P.

---

One can tell an even simpler (and amusing, but also potentially even
more misleading) story based on puzzles. With just a few constraints,
one can force a lot of search to be done, for instance NxN Sudoku
is NP-complete. Now consider being asked to solve lots of small
puzzles as a single instance, in one go (e.g. many 9x9 Sudokus).
The time taken is going to be roughly linear in the number of puzzles
in each instance, and this problem is then in P. For intermediate
problems, one can think of each instance being a largish (but not
too large) number of Sudokus on largish (but not too large) grids.
The reason we don't observe many such problems is because they would be
dreary to pose and to solve!

> **Comments:**
> **username_1**: Here is some further technical meat to add to your "core of hardness" story. N. Lynch (1975) defined a p-complexity core for a language $L$ to be a set of strings $C$ such that for all algorithms that correctly decide $L$ on all inputs, for all $k$, the algorithm runs in time $n^k + k$ on only finitely many inputs from $C$. Lynch showed that every $L \notin \mathsf{P}$ has a p-complexity core, and Orponen and Schoning showed that every such $L$ has a core that is not polynomially sparse. One might (*might*) hypothesize that languages in NP with sufficiently dense cores have to be NP-complete.  
> **username_4**: The references Joshua mentioned: Lynch: http://dx.doi.org/10.1145/321892.321895 and Orponen-Schöning: http://dx.doi.org/10.1016/S0019-9958(86)80024-9 also see Orponen-Ko-Schöning-Watanabe: http://dx.doi.org/10.1145/174644.174648  

---

### Answer by username_0 on 2014-02-10. Score: 2

Several answers pointed out that the premise of my question (the relative scarcity of natural $\mathsf{NPI}$-candidates) might be questionable. After some thinking, I must accept that they indeed have a point. In fact, one can even go as far as to make the case that there are actually  *more*  natural $\mathsf{NPI}$ candidates than natural $\mathsf{NP}$-complete problems. The argument could go as follows.

Consider the LOGCLIQUE problem, which aims at deciding whether an $n$-vertex input graph has a clique of size $\geq \log n$. This is a natural $\mathsf{NPI}$ candidate. Now, the same type of "scaling down" can be carried out on  *any*  $\mathsf{NP}$-complete problem. Simply replace the question "does the input string $x$ have a property $Q$?" by the scaled down question "does $x$ have a logarithmically sized substring that has property $Q$?" (We may restrict ourselves only to those substrings that represent the appropriate type of structure, such as subgraphs etc.)
Arguably, if the original problem was natural, the scaling down does not change this, since we only alter the size of what is sought for. The resulting problem will be an $\mathsf{NPI}$ candidate, since it is solvable in quasi-polynomial time, but still unlikely to fall into $\mathsf{P}$, as the mere size restriction probably does not introduce new structure.

This way, we can construct a natural $\mathsf{NPI}$ candidate for  *every*  natural $\mathsf{NP}$-complete problem. Additionally, there are also generic candidates that do not arise via scaling down, such as Graph Isomorphism, Factoring etc. Thus, one can indeed make the case that "natural-$\mathsf{NPI}$" is actually more populous than "natural $\mathsf{NPC}$."

Of course, this scaling down process, using Scott's nice metaphor, gives an obvious reason for resisting the "gravitational pull" of SAT. While there are papers published about LOGCLIQUE and similar problems, they did not draw too much attention, as these problems are less exciting than the the generic $\mathsf{NPI}$ candidates, where there is no clear understanding of how the gravitational pull is resisted, without falling into $\mathsf{P}$.

> **Comments:**
> **username_4**: Your argument seems fine for problems in $W[1]$, but it seems to fail higher up in the W-hierarchy.  Yet you contend that this works for "_every_ natural NP-complete problem".  What am I missing?  
> **username_0**: My understanding is that the scaling down can be done independently from any parametrization. If the original problem asks  "does the input string $x$ have a property $Q$?" then you can always replace it by the question "does $x$ have a $O(\log |x|)$ sized substring that has property Q?" I do not see the relationship with parametrized complexity.  
> **username_4**: For 3-COLOURING, what is the scaled down version of the problem?  
> **username_0**: For 3-COLORING the scaled down version is this: does the $n$-vertex input graph contain a 3-colorable subgraph with at least $\log n$ vertices?  
> **username_1**: I understand that the scaling down works for any problem, but I would argue that it's only *natural* for problems that are (naturally) parametrized to begin with. Viz: LOGCLIQUE is fairly natural, but "Does a graph on $n$ vertices have a $\log n$-sized subgraph that is 3-colorable?" doesn't seem natural to me, because the original problem had nothing to do with finding a widget (e.g. clique) of a certain size.  
> **username_0**: "Naturalness" is indeed a rather elusive concept. Nevertheless, I do not see why the property "being a clique" is more natural than "being 3-colorable."  Once we accept that these are equally natural properties, then looking for a $\log n$-vertex subgraph with the property appears (to me) equally natural for both properties.  
> **username_1**: It's not the difference b/w "being a clique" and "being 3-colorable". It's the difference between the original problem being: 1) does a graph have a subgraph with some property of a given size (e.g. CLIQUE) vs. 2) does a graph have a property. In the case of (1), changing the size to be log is natural, b/c the *size* of the subgraph was already part of the question. When you do your trick to (2), you *add in* the size of the subgraph as a new part of the problem.  
> **username_0**: We may state 3-colorability this way: does the graph have 3 disjoint independent sets, such that the sum of their sizes is at least $k$?  Then with $k=n$ we get the original problem, with $k=\log n$ we get the scaled down version.  
> **username_1**: Interesting! I hadn't thought of that. Given the plethora of NP-complete problems, I'd still think there are many that cannot be phrased with such a natural parameter (even though your trick works regardless).  
> **username_0**: Technically, all graph problems where we want to decide whether the input graph has a property $Q$, can be phrased this way: does the graph have a subgraph on $\geq k$ vertices with property $Q$? Then with $k=n$ we get the original problem, with $k=\log n$ the scaled down version. Once the property $Q$ is accepted as natural, there seems to be no reason to view it "more natural" for certain values of $k$, than for others. Then from here it is only one step to apply this for general input strings, rather than graphs, so that we may include any NP-complete problem.  
> **username_4**: I'm provisionally prepared to accept that this works for constraint satisfaction problems (which cover most graph problems in NP), since one can always weaken the problem by asking for a partial homomorphism of logarithmic size instead of a homomorphism.  (In other words, every CSP has a natural weakening in this way.)  However, what about problems in NP that are not known to be naturally expressible as CSPs, such as Partition, Integer Linear Programming, Factoring, or Regular Grammar Inequivalence?  
> **username_0**: Let us take the Partition problem, as an example. Here the input is a set $S$ of  numbers, and the question is whether there is a subset $A$, such that the sum of numbers in $A$ is the same as in $S-A$. The scaled down version would be this: let $n=|S|$; is there a $\geq \log n$-sized subset $S'$ of $S$, such that there is a solution to Partition on $S'$?  
> **username_4**: OK, and moreover ILP is a CSP with an infinite domain.  That leaves Factoring and Regular Grammar Inequivalence.  For problems like these, I don't see what a natural "subproblem" would be, so how does your scaling argument work in those cases?  
> **username_4**: Your statement "we can construct a natural NPI candidate for every natural NP-complete problem" seems to be too strong.  Characterizing a _subclass of NP_ for which we can do this seems worthwhile, via a formalisation of your "scaling down" argument, but I'm not yet convinced that the argument applies to all of NP.  
> **username_0**: I think, it can be applied to all of NP in the following way. $Every$    problem in NP is presentable in the following format: given an input string $x$, does there exist another string $y$, such that $|y|\leq p(|x|)$, and $(x,y)\in L$, where $L$ is a polynomial-time decidable language, and $p$ is a polynomial. Now, the scaled down version is this:  does there exist a substring $x'$ of $x$, such that $|x'|\geq \log |x|$, and there exist another string $y'$ with $|y'|\leq p(|x'|)$ and $(x',y')\in L$.  

---

