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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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!

Answer 6

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