Should reductions make us more or less optimistic for the tractability of a problem?

Question

It seems to me that most complexity theorists generally believe the following philosophical rule:

If we can't figure out an efficient algorithm for problem $A$, and we can reduce problem $A$ to problem $B$, then there probably isn't an efficient algorithm for problem $B$, either.

This is why, for example, when a new problem is proved NP-Complete we simply file it away as "too hard" rather than getting excited about a new approach (problem $B$) that might finally show $P = NP$.

I was discussing this with a fellow grad student in another scientific field. She found this idea hugely counterintuitive. Her analogy:

You're an explorer, searching for a bridge between the North American and Asian continents. For many months you have tried and failed to find a land bridge from the mainland United States area to Asia. Then you discover that the mainland US is connected by land to the Alaskan area. You realize that a land bridge from Alaska to Asia would imply a land bridge from the mainland US to Asia, which you're pretty sure doesn't exist. So you don't waste time exploring near Alaska; you just go home.

Our previous philosophical rule sounds pretty silly in this context. I couldn't think of a good rebuttal! So I'm turning it over to you guys: Why should we treat a reduction $A \to B$ as making problem $B$ harder rather than making problem $A$ easier?

Answer 1

I think this is a very good question. To answer it we need to realise that:

• not all reductions are alike,
• to feel optimistic, we need to learn something genuinely helpful.

Typically, whenever we discover a nontrivial reduction $A \to B$, it falls in one of the following categories:

1. We learned something helpful about problem A (and nothing about problem B).
2. We learned something discouraging about problem B (and nothing about problem A).

A bit more precisely, these two cases can be characterised as follows:

1. We discovered that problem A has some hidden structure, which makes it possible to design a new, clever algorithm for solving problem A. We just need to know how to solve problem B.

2. We realised that in some special cases, problem B is basically just problem A in disguise. We can now see that any algorithm for solving problem B has to solve at least these special cases correctly; and solving these special cases is essentially equivalent to solving problem A. We are back at square one: to make any progress with problem B, we need to first make some progress with problem A.

Reductions of type 1 are common in the context of positive results, and these are certainly good reasons to feel optimistic.

However, if you consider hardness reductions that we encounter in the context of, e.g., NP-hardness proofs, they are almost always of type 2.

Note that even if you do not know anything about the computational complexity of problem A or problem B, you can nevertheless tell if your reduction is of type 1 or type 2. Hence we do not need to believe in, e.g., P ≠ NP to determine if we should feel optimistic or pessimistic. We can just see what we have learned thanks to the reduction.

Answer 2

What is missing from the analogy is some notion of the relative distances involved. Let's replace Alaska in our analogy with the moon:

You're an explorer, searching for a bridge between the North American and Asian continents. For many months you have tried and failed to find a land bridge from the mainland United States area to Asia. Then you discover that the mainland US is connected by land to the moon. You are already confident that the moon is a vast distance away from Asia, so you can now be confident that North America is also a vast distance away from Asia by the triangle inequality.

Answer 3

It is not true that we always look at reduction theorems as hardness statements. For example, in algorithms we often reduce a problem to LP and SDP to solve them. These are not interpreted as hardness results but algorithmic results. However, although they are technically reductions we often don't refer to these as such. What we mean by a reduction is usually a reduction to some (NP-)hard problem.

A reduction is a relative hardness result, if we have a reduction from problem $A$ to problem $B$ is means that $A$ is easier than $B$ in a sense, which is the same as $B$ is more difficult than $A$. A lower-bound is an absolute hardness result. Now if we know/conjecture that $A$ is absolutely hard then the reduction from $A$ to $B$ implies the same for $B$. Most researchers find it more likely that P is not equal to NP, and even conjecture that SAT requires exponential time. In other words SAT is believed to be very hard. If you accept these conjectures then it is completely reasonable to look at reductions proving universality of a problem for NP as the problem being hard. (Why researchers find P not equal to NP more likely is a different issue, there has been several blog posts on theory blogs about that.)

Part of the reason we replace lower-bound with universality results (i.e. there is a reduction from every problem in a class to the problem) is our lack of success in proving good general lower-bounds (it is consistent with the current state of knowledge that SAT can be solved in linear deterministic time).

Answer 4

Actually, the discovery of Alaska would have the opposite effect, at least at first. Since it extends so far west, it would make people think that, hey, maybe there is a land bridge, after all (the analogy being, hey, maybe P = NP since this new NP-complete problem looks like such a good candidate for having a polynomial-time solution). However, once Alaska had been thoroughly explored and no land bridge had been found, people would probably be more convinced than before that Asia and the Americas are separate.

Answer 5

the question introduces a particular analogy/metaphor not used much by experts and focuses only on P/NP & does not mention any other complexity classes, whereas experts tend to see it as a large interconnected universe of entities as in the remarkable diagram created by Kuperberg. it would be neat to compile a large list of analogies of complexity classes, there are many such analogies. it talks about "filing away" problems proven as NP complete and "excitement over new approaches".

one can understand that there was initial "excitement" on discovering the NP complete class, but some "excitement" has faded after now over four decades of intense effort to prove P≠NP seems not to have gone anywhere promising and some researchers feel that we are no closer. history is full of researchers who spent long years working on problems without any or much apparent progress sometimes with later regret. so NP complete can serve (to borrow Aaronson's analogy) as a sort of "electric fence", a warning/caveat not to get too involved in attempts on (here literally, in more ways than one) "intractable" problems.

it is true there is a major aspect of "cataloging" NP complete problems that still continues. however massive "finer-grained" research on key NP complete problems (SAT, clique detection, etc) continues. (actually a very similar phenomenon occurs wrt undecidable problems: once proven undecidable, its as if they are ruled a "no mans land" for further inquiry.)

so all NP complete problems are proven equivalent as far as current theory and this sometimes shows in striking conjectures such as the Berman-Hartmanis isomorphism conjecture. researchers are hopeful that this will change someday.

this question is labelled soft-question with good reason. you will not find serious scientists much discussing analogies in their papers, which veers into popular science, preferring instead to focus on mathematical precision/rigor (and as emphasized in the communication guidelines for this group). nevertheless there is some value here for educating & communicating with outsiders/laymen.

here are a few "counter-analogies" for laymen along with "research leads" to the concepts. this could be made into a longer list.

• there is an analogy of territories in the question. but it makes more sense to think of major regions of complexity theory including within known classes as terra incognita. in other words there is a region of P intersect NP. both P and NP are fairly well understood but it is not known if the region P ⋂ NP-hard (P intersect NP-hard) is empty or not.

• Aaronson recently gave the metaphor of two apparently different types of frog species that never mix for P/NP. he also referred to the "invisible electric fence" between the two.

• particle physics studies the standard model. physics studies the composition of particles just as complexity theory studies the composition of complexity classes. in physics there is some uncertainty about how some particles give rise to others ("establishing boundaries") just as in complexity theory.

• "the complexity zoo", its like a lot of exotic animals that have different capabilities, some small/weak & some large/powerful.

• complexity classes are like a smooth time/space continuum as seen in the Time/Space hierarchy theorems with key "transition points" (surprisingly quite deeply analogous to physical matter phase transitions) between the various states.

• a Turing machine is a machine with "moving parts" and machines do work which is equivalent to energy measurements, and they have time/space measurements. so complexity classes can be seen as "energy" associated with black box input-output transformations.

• there are many possible analogs from Mathematics history ie the problem of squaring the circle, finding algebraic solutions to the quintic equation, etcetera.

• Impaggliazo's worlds

• Fortnows new book contains much popular science analogy for mining.

• Encryption/Decryption: Turing famously worked on this during WWII and a lot of theorem proving about differences in complexity classes might seem analogous to decryption problems. this is made more solid with papers like Natural Proofs where complexity class separation is related directly to "breaking" pseudo random number generators.

• Compression/decompression: different complexity classes allow for/represent different amounts of data compression. for example suppose P/poly contains NP. that would mean that there are "smaller" entities (namely circuits) that can "encode" "larger" NP complete problems, ie the larger (data) structures can be "compressed" efficiently into smaller (data) structures.

• along the zoo/animal analogy, there is a strong Blind man and elephant aspect to complexity theory. the field is still apparently/possibly in its earlier stages of a very long arc (this is not implausible or unheard-of wrt other math fields that have spans of centuries or even millenia) and much knowledge can be seen as partial, disjoint, and fragmented.

so in short the question asks about "optimism associated with reductions". scientists generally refrain from emotions or even laugh at them at times in their purely logical search. there is a balance of both longterm pessimism and cautious optimism in the field & while there is some room for informality, all serious researchers should strive toward impartiality in their professional attitudes as part of the job description. understandably there is a focus on small victories and incrementalism and not getting "carried away".