# Why are so few natural candidates for NP-intermediate status?

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

• Um, the length of the diagonal of a 1cm x 1cm square is an irrational number... – Joshua Grochow Feb 8 '14 at 1:36
• 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 Feb 8 '14 at 1:42
• 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 Feb 8 '14 at 2:30

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, but (as another commenter already pointed out) there are other possible answers that I missed.

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

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 !

... 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, Discrete Applied Mathematics, Volume 136, Issue 1, 30 January 2004, Pages 3-11, ISSN 0166-218X.

• However, it cannot be filled with $(2+\varepsilon)$-SAT: eccc.hpi-web.de/report/2013/159 – Joshua Grochow Feb 11 '14 at 0:26
• @JoshuaGrochow: my reference for the "sauce" is the Zhao, Deng, Lee and Zhu paper "$(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 Feb 11 '14 at 7:36
• The definitions of $(2+f(n))$-SAT in the two papers are different; I think both are correct! – Joshua Grochow Feb 11 '14 at 14:55
• @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 Mar 14 '14 at 2:48

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

• why do these CSP problems not fall under the dichotomy conjecture? – Sasho Nikolov Feb 8 '14 at 15:11
• 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 Feb 8 '14 at 15:15
• @JoshuaGrochow I'am afraid that it is arguable as there is no formal notion for what natural means. – Mohammad Al-Turkistany Feb 8 '14 at 15:32
• @SashoNikolov Do you mean the dichotomy conjecture of Feder and Vardi? – Mohammad Al-Turkistany Feb 8 '14 at 15:34
• @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 Feb 10 '14 at 9:54

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!

• 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 Feb 11 '14 at 0:24
• The references Joshua mentioned: Lynch: dx.doi.org/10.1145/321892.321895 and Orponen-Schöning: dx.doi.org/10.1016/S0019-9958(86)80024-9 also see Orponen-Ko-Schöning-Watanabe: dx.doi.org/10.1145/174644.174648 – András Salamon Feb 11 '14 at 22:33

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

• 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 Feb 10 '14 at 20:38
• 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 Feb 10 '14 at 22:32
• For 3-COLOURING, what is the scaled down version of the problem? – András Salamon Feb 10 '14 at 23:38
• 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 Feb 11 '14 at 0:03
• 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 Feb 11 '14 at 0:28