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

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

CC BY-SA 3.0
2014-03-31T23:59:14.540Z
+1. This answer brings out a deeper point. Reductions can both "pull things apart" as well as "bring them together". Which of them it appears to do depends on your prior belief.
Suresh Venkat
CC BY-SA 3.0
2014-03-31T23:49:12.483Z
2014-03-31T23:49:12.483Z
Geoffrey Irving
<p>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.</p>

<p>A reduction is a <em>relative</em> 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 <em>absolute</em> 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.)</p>

<p>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). </p>

CC BY-SA 3.0
2014-04-01T21:42:09.187Z
A is easier than B?  Most reductions involve a certain time penalty, and it's quite possible that a particular reduction might be as fast as the fastest solution to A.  A reduction from A to B shows that A isn't very much harder than B, but it might still be harder.
Brilliand
CC BY-SA 3.0
2014-04-02T04:14:42.110Z
Easier here means up to equivalence class of the class of reductions.
Kaveh
CC BY-SA 3.0
2014-04-02T16:10:53.230Z
It's possible for two problems to be mutually easier than each other?  I get generalizing to equivalence classes, but I'd think that should still be "at least as easy as".
Brilliand
CC BY-SA 3.0
2014-04-02T16:37:45.263Z
Easier doesn't mean strictly easier.
Kaveh
CC BY-SA 3.0
2014-03-31T23:40:35.647Z
2014-04-01T09:45:31.337Z
2014-04-01T09:45:31.337Z
Kaveh
<p>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 <em>is</em> a land bridge, after all (the analogy being, hey, maybe <strong>P</strong>&nbsp;=&nbsp;<strong>NP</strong> since this new <strong>NP</strong>-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.</p>

CC BY-SA 3.0
2014-04-01T07:55:24.210Z
2014-04-01T07:55:24.210Z
David Richerby
<p>the question introduces a particular analogy/metaphor not used much by experts and focuses only on P/NP &amp; does not mention any other complexity classes, whereas experts tend to see it as a large interconnected universe of entities as in the <a href="http://www.math.ucdavis.edu/~greg/zoology/diagram.pdf" rel="nofollow noreferrer">remarkable diagram created by Kuperberg</a>. 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". </p>

<p>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/<em>caveat</em> not to get too involved in attempts on (here literally, in more ways than one) "intractable" problems.</p>

<p>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.)</p>

<p>so all NP complete problems are proven equivalent <em>as far as current theory</em> and this sometimes shows in striking conjectures such as the <a href="http://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture" rel="nofollow noreferrer">Berman-Hartmanis</a> isomorphism conjecture. researchers are hopeful that this will change someday. </p>

<p>this question is labelled <code>soft-question</code> with good reason. you will not find serious scientists much discussing analogies in their papers, which veers into <a href="https://cstheory.stackexchange.com/questions/18968/">popular science</a>, 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 &amp; communicating with outsiders/laymen.</p>

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

<ul>
<li><p>there is an analogy of territories in the question. but it makes more sense to think of major regions of complexity theory including <em>within</em> known classes as <em>terra incognita</em>. 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.</p></li>
<li><p><a href="http://www.scottaaronson.com/blog/?p=1720" rel="nofollow noreferrer">Aaronson</a> 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.</p></li>
<li><p>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.</p></li>
<li><p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo" rel="nofollow noreferrer">"the complexity zoo"</a>, its like a lot of exotic animals that have different capabilities, some small/weak &amp; some large/powerful.</p></li>
<li><p>complexity classes are like a smooth time/space continuum as seen in the <a href="http://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="nofollow noreferrer">Time</a>/<a href="http://en.wikipedia.org/wiki/Space_hierarchy" rel="nofollow noreferrer">Space</a> hierarchy theorems with key <a href="http://www.cse.unsw.edu.au/~tw/phase.ppt" rel="nofollow noreferrer">"transition points"</a> (surprisingly quite deeply analogous to physical matter phase transitions) between the various states.</p></li>
<li><p>a Turing machine is a <em>machine</em> with "moving parts" and machines do <em>work</em> which is equivalent to <em>energy</em> measurements, and they have <em>time/space</em> measurements. so complexity classes can be seen as <a href="https://cstheory.stackexchange.com/questions/4204/">"energy"</a> associated with black box input-output transformations.</p></li>
<li><p>there are many possible analogs from <a href="https://mathoverflow.net/questions/160265/analogues-of-p-vs-np-in-the-history-of-mathematics">Mathematics history</a> ie the problem of squaring the circle, finding algebraic solutions to the quintic equation, etcetera.</p></li>
<li><p><a href="http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds" rel="nofollow noreferrer">Impaggliazo's worlds</a></p></li>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/0691156492" rel="nofollow noreferrer">Fortnows new book</a> contains much popular science analogy for mining.</p></li>
<li><p>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 <a href="http://en.wikipedia.org/wiki/Natural_proof" rel="nofollow noreferrer">Natural Proofs</a> where complexity class separation is related directly to "breaking" pseudo random number generators.</p></li>
<li><p>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.</p></li>
<li><p>along the zoo/animal analogy, there is a strong <a href="http://en.wikipedia.org/wiki/Blind_men_and_an_elephant" rel="nofollow noreferrer">Blind man and elephant</a> 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.</p></li>
</ul>

<p>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 &amp; 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".</p>

CC BY-SA 3.0
2014-04-01T18:07:34.607Z
Thanks, this is a great response.  What a fantastic diagram by Kuperberg!
GMB
CC BY-SA 3.0
2014-04-02T16:39:27.540Z
yes. hopefully that should make it more clear that reductions are a mechanism to assign (previously unknown) problems within a "master classification system" somewhat like phylum/species etc in biology. this generally supports rather than precludes further study. also in the diagram, the continuum of computational hardness ranges from "low/easy" on the bottom to "hard" at the top. what is remarkable is the contrast/dichotomy of discrete and continuous aspects of the class hierarchy. also, major/key classes like P/NP function something like "hubs" with many other classes related to them.
vzn
CC BY-SA 3.0
2014-04-01T15:50:24.147Z
2014-04-01T15:57:01.090Z
2017-04-13T12:57:54.530Z
vzn
<p>I think this is a very good question. To answer it we need to realise that:</p>

<ul>
<li>not all reductions are alike,</li>
<li>to feel optimistic, we need to learn something genuinely helpful.</li>
</ul>

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

<ol>
<li>We learned something helpful about problem A (and nothing about problem B).</li>
<li>We learned something discouraging about problem B (and nothing about problem A).</li>
</ol>

<p>A bit more precisely, these two cases can be characterised as follows:</p>

<ol>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ol>

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

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

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

CC BY-SA 3.0
2014-04-01T15:22:10.943Z
I like this answer a lot.  It sounds to me like it would take a lot of experience in the field to distinguish between type-1 reductions and type-2 reductions.  Do you know if there are any good historical examples of this?  For example, were there any NP-Completeness results that were structurally deep enough that people considered $P=NP$?
GMB
CC BY-SA 3.0
2014-04-01T09:00:44.257Z
2014-04-01T09:00:44.257Z
Jukka Suomela
<p>It seems to me that most complexity theorists generally believe the following philosophical rule:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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$.</p>

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

<blockquote>
  <p>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.</p>
</blockquote>

<p>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: <strong>Why should we treat a reduction $A \to B$ as making problem $B$ harder rather than making problem $A$ easier?</strong></p>

CC BY-SA 3.0
2014-04-01T00:03:26.260Z
BTW, every single time we write a subroutine we're asserting that $A \rightarrow B$ makes $A$ easier.
Suresh Venkat
CC BY-SA 3.0
2014-04-01T05:00:01.703Z
P/NP are only the most "well known" complexity classes & those taught to neophytes. its an entire universe thats slowly being mapped out from "tiny" to "large". the reductions are largely preparing for the day, not yet here, when major classes can be discriminated from each other with greater precision than is now possible/available. maybe this question can be answered with other intuitive analogies. one possible scientific analogy is that complexity classes are to TCS as (fundamental) particles are to physics. & we are still attempting to determine the interrelations. etc... may answer later.
vzn
CC BY-SA 3.0
2014-04-01T07:32:17.337Z
@vzn Please don't describe grad students as "neophytes": it has rather negative connotations. Even "beginner" doesn't give enough credit.
David Richerby
CC BY-SA 3.0
2014-04-01T09:04:23.207Z
I found a few examples - but I think there are many of them - in which the reduction is *explicitly* used "in the opposite (positive) direction": use a polynomial time problem $B$ to model a problem $A$ (i.e. find a reduction $A \leq_m B$) proving in this way that $A$ can be solved in polynomial time. I remember this about planning problems: **Theorem 3.10**: The blocks-world problem can be reduced to $PLANSAT_1^+$ (which is polynomial time solvable)
in Tom Bylander: The Computational Complexity of Propositional STRIPS Planning. Artif. Intell. 69(1-2): 165-204 (1994)
Marzio De Biasi
CC BY-SA 3.0
2014-04-01T16:16:06.493Z
fine, but lets not forget the geographic analogy quoted was _introduced by a grad student from another field_ which imho counts as a _neophyte_ wrt complexity theory, with no negative connotations intended there & maybe [even some positive ones](http://en.wikipedia.org/wiki/Beginners_Mind) :)
vzn
CC BY-SA 3.0
2014-04-01T17:09:16.013Z
There is an interesting example with the planted clique problem: [Frieze and Kannan](http://www.math.cmu.edu/~af1p/Texfiles/planted.pdf) showed that finding a planted clique in a random graph can be reduced to approximating the maximum of a cubic form, for random instances. In the paper they clearly present their result as an approach to planted clique. As far as I know, currently this reduction is usually seen as evidence for the hardness of problems on 3-dimensional tensors.
Sasho Nikolov
CC BY-SA 3.0
2014-04-01T19:27:45.013Z
@vzn However well-meant, "neophyte" comes across like "noob". Just don't.
David Richerby
CC BY-SA 3.0
2014-04-01T22:26:00.403Z
for those unaware, [defn neophyte](http://dictionary.reference.com/browse/neophyte). (def1!) [feel it was a "softer" response than the endless criticism about "not a research question" or "not mathematically rigorous" etc that goes on around here....] the question might be interpreted as that the questioner is only familiar with NP complete reductions so far (which indeed can be a misconception by _neophytes_...) short answer, if you reduce to a P problem or "smaller" you can be "optimistic" about tractability. if you reduce to a NP problem or harder (eg Exptime) you can be "pessimistic". :p
vzn
<cc.complexity-theory><big-picture><reductions>
Should reductions make us more or less optimistic for the tractability of a problem?
GMB
# Should reductions make us more or less optimistic for the tractability of a problem?

(Asked by: username_0 on 2014-03-31)

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

**Tags:** cc.complexity-theory, big-picture, reductions
> **Comments:**
> **username_1**: BTW, every single time we write a subroutine we're asserting that $A \rightarrow B$ makes $A$ easier.  
> **username_2**: P/NP are only the most "well known" complexity classes & those taught to neophytes. its an entire universe thats slowly being mapped out from "tiny" to "large". the reductions are largely preparing for the day, not yet here, when major classes can be discriminated from each other with greater precision than is now possible/available. maybe this question can be answered with other intuitive analogies. one possible scientific analogy is that complexity classes are to TCS as (fundamental) particles are to physics. & we are still attempting to determine the interrelations. etc... may answer later.  
> **username_3**: @vzn Please don't describe grad students as "neophytes": it has rather negative connotations. Even "beginner" doesn't give enough credit.  
> **username_4**: I found a few examples - but I think there are many of them - in which the reduction is *explicitly* used "in the opposite (positive) direction": use a polynomial time problem $B$ to model a problem $A$ (i.e. find a reduction $A \leq_m B$) proving in this way that $A$ can be solved in polynomial time. I remember this about planning problems: **Theorem 3.10**: The blocks-world problem can be reduced to $PLANSAT_1^+$ (which is polynomial time solvable) in Tom Bylander: The Computational Complexity of Propositional STRIPS Planning. Artif. Intell. 69(1-2): 165-204 (1994)  
> **username_2**: fine, but lets not forget the geographic analogy quoted was _introduced by a grad student from another field_ which imho counts as a _neophyte_ wrt complexity theory, with no negative connotations intended there & maybe [even some positive ones](http://en.wikipedia.org/wiki/Beginners_Mind) :)  
> **username_5**: There is an interesting example with the planted clique problem: [Frieze and Kannan](http://www.math.cmu.edu/~af1p/Texfiles/planted.pdf) showed that finding a planted clique in a random graph can be reduced to approximating the maximum of a cubic form, for random instances. In the paper they clearly present their result as an approach to planted clique. As far as I know, currently this reduction is usually seen as evidence for the hardness of problems on 3-dimensional tensors.  
> **username_3**: @vzn However well-meant, "neophyte" comes across like "noob". Just don't.  
> **username_2**: for those unaware, [defn neophyte](http://dictionary.reference.com/browse/neophyte). (def1!) [feel it was a "softer" response than the endless criticism about "not a research question" or "not mathematically rigorous" etc that goes on around here....] the question might be interpreted as that the questioner is only familiar with NP complete reductions so far (which indeed can be a misconception by _neophytes_...) short answer, if you reduce to a P problem or "smaller" you can be "optimistic" about tractability. if you reduce to a NP problem or harder (eg Exptime) you can be "pessimistic". :p  

---

## 5 answers

### Answer by username_9 on 2014-04-01. Score: 14 | Accepted answer

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.

> **Comments:**
> **username_0**: I like this answer a lot.  It sounds to me like it would take a lot of experience in the field to distinguish between type-1 reductions and type-2 reductions.  Do you know if there are any good historical examples of this?  For example, were there any NP-Completeness results that were structurally deep enough that people considered $P=NP$?  

---

### Answer by username_6 on 2014-03-31. Score: 16

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.

> **Comments:**
> **username_1**: +1. This answer brings out a deeper point. Reductions can both "pull things apart" as well as "bring them together". Which of them it appears to do depends on your prior belief.  

---

### Answer by username_7 on 2014-03-31. Score: 9

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

> **Comments:**
> **username_8**: A is easier than B?  Most reductions involve a certain time penalty, and it's quite possible that a particular reduction might be as fast as the fastest solution to A.  A reduction from A to B shows that A isn't very much harder than B, but it might still be harder.  
> **username_7**: Easier here means up to equivalence class of the class of reductions.  
> **username_8**: It's possible for two problems to be mutually easier than each other?  I get generalizing to equivalence classes, but I'd think that should still be "at least as easy as".  
> **username_7**: Easier doesn't mean strictly easier.  

---

### Answer by username_3 on 2014-04-01. Score: 3

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 by username_2 on 2014-04-01. Score: 3

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](http://www.math.ucdavis.edu/~greg/zoology/diagram.pdf). 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](http://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture) 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](https://cstheory.stackexchange.com/questions/18968/), 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](http://www.scottaaronson.com/blog/?p=1720) 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"](https://complexityzoo.uwaterloo.ca/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](http://en.wikipedia.org/wiki/Time_hierarchy_theorem)/[Space](http://en.wikipedia.org/wiki/Space_hierarchy) hierarchy theorems with key ["transition points"](http://www.cse.unsw.edu.au/~tw/phase.ppt) (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"](https://cstheory.stackexchange.com/questions/4204/) associated with black box input-output transformations.
* there are many possible analogs from [Mathematics history](https://mathoverflow.net/questions/160265/analogues-of-p-vs-np-in-the-history-of-mathematics) ie the problem of squaring the circle, finding algebraic solutions to the quintic equation, etcetera.
* [Impaggliazo's worlds](http://intractability.princeton.edu/blog/2009/05/program-for-workshop-on-impagliazzos-worlds)
* [Fortnows new book](http://rads.stackoverflow.com/amzn/click/0691156492) 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](http://en.wikipedia.org/wiki/Natural_proof) 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](http://en.wikipedia.org/wiki/Blind_men_and_an_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".

> **Comments:**
> **username_0**: Thanks, this is a great response.  What a fantastic diagram by Kuperberg!  
> **username_2**: yes. hopefully that should make it more clear that reductions are a mechanism to assign (previously unknown) problems within a "master classification system" somewhat like phylum/species etc in biology. this generally supports rather than precludes further study. also in the diagram, the continuum of computational hardness ranges from "low/easy" on the bottom to "hard" at the top. what is remarkable is the contrast/dichotomy of discrete and continuous aspects of the class hierarchy. also, major/key classes like P/NP function something like "hubs" with many other classes related to them.  

---

