<p>Russell Impagliazzo published <a href="http://dx.doi.org/10.1109/SCT.1995.514853" rel="nofollow noreferrer">"A Personal View of Average-Case Complexity"</a> (<a href="http://cseweb.ucsd.edu/~russell/average.ps" rel="nofollow noreferrer">preprint</a>) back in 1995.
He presented five possible worlds we could be living in, depending on how P and NP were related.
The first world presented is Algorithmica, in which P = NP, "or some moral equivalent" such as NP being contained in BPP, or NP = RP ≠ P.
The remaining four worlds are all variants where P ≠ NP, and they are "morally" different, with differences between the algorithmic applications of hardness differntiating the worlds.</p>

<p>It seems to me that there is a large landscape inside Algorithmica, and I'm wondering:</p>

<blockquote>
  <p>has anyone written about Algorithmica in more detail?</p>
</blockquote>

<p>The best reference I have found so far is a <a href="https://rjlipton.wordpress.com/2009/07/03/is-pnp-an-ill-posed-problem/" rel="nofollow noreferrer">blog post by Richard Lipton from 2009</a> which briefly explores Algorithmica but doesn't go into much detail.</p>

<hr>

<p>Although it seems unlikely that we are living in Algorithmica, understanding that landscape might still motivate interesting work.
For instance, it might highlight precisely what the world would have to look like for quantum factoring to be rendered irrelevant, or if quantum factoring is ignored, where classical factoring might still be challenging.
See the related question <a href="https://cstheory.stackexchange.com/q/1026/109">Status of Impagliazzo's Worlds?</a> for a discussion focused on the other parts of the landscape, including Boaz Barak's summary of a 2009 workshop about Impagliazzo's multiverse.</p>

CC BY-SA 3.0
2016-02-18T05:23:01.907Z
It's funny (or maybe sad) to imagine the average STOC reviewer's response to a paper starting "Under the assumption $\mathsf{NP} \subseteq \mathsf{BPP}$, we show ...."
usul
CC BY-SA 3.0
2016-02-18T18:59:16.877Z
Let $n$ be the highest number that will ever been computed (in binary representation) by a device built by the humans; there exits a (much much smaller) busy beaver $B$ of length $b$ such that $\Sigma(b)>n$ (the busy beaver function). There exists a slightly larger machine $M$ that runs in time  $O(1)$ and on input $x$ operates as follow: simulate $B$ and if $x < \Sigma(b)$ then treat $x$ as a SAT formula and solve it using an exhaustive search, otherwise reject ... a non-constructive proof that a bunch of bits (probably less than 4242) can solve ("human") SAT in constant time :-D :-D
Marzio De Biasi
CC BY-SA 3.0
2016-02-18T19:46:51.807Z
most researchers believe P!=NP wrt [Gasarch 2012 survey](https://www.cs.umd.edu/~gasarch/papers/poll2012.pdf). so algorithmica is regarded as unlikely. there is some consideration at length in [golden ticket](http://www.amazon.com/The-Golden-Ticket-Search-Impossible/dp/0691156492) by Fortnow, but it seems mostly speculative/ unsourced. actually this is all covered fairly well in this question [what would be the real world implications of a P=NP proof](http://cs.stackexchange.com/questions/35759/what-would-be-the-real-world-implications-of-a-constructive-p-np-proof) / [cs.se]
vzn
CC BY-SA 3.0
2016-02-18T19:50:24.940Z
Joking apart, I just remembered that the whole Chapter 2 of "The Golden Ticket" by L. Fortnow is dedicated to Algorithmica: **Chapter 2 - The Beautiful World** *... To give you a tiny taste of this beautiful world, let's imagine a future world a few years after the discovery of an efficient algorithm that solves NP problems. Let's jump to the year 2026 and explore this beautiful world, almost surely a fantasy world, the world of P=NP. First let's see how this world developed ...* ... then he (informally) describes a few consequences of such discovery (e.g. medical research progress ).
Marzio De Biasi
CC BY-SA 3.0
2016-02-18T23:19:58.400Z
Thanks for the additional pointers.  I was aware of the CS.SE question.  Trying to write a new answer to it, a map of Algorithmica was an obvious thing to already exist.  Yet I couldn't find it: hence this question.  There are many consequences of P=NP (quite possibly even every utterly false thing) but they live in several regions that are as different from each other as Algorithmica is from Impagliazzo's four other lands.  It is this structure I am interested in.  For instance, in some regions of Algorithmica the RSA cryptosystem seems perfectly viable, while in another factoring is trivial.
András Salamon
CC BY-SA 3.0
2016-02-19T16:26:47.680Z
Not to point out the obvious, but as Yogi Berra might say, a barrier to these kinds of results is the lack of research about them. Namely, in a world of $P \neq NP$ we have a lot of work on identifying and using further assumptions, which allow the separations between the other four worlds. Before getting off the ground, research into Algorithmica might have to do the same. But it might be hard to justify or pick such assumptions if we don't think they're true....
usul
CC BY-SA 3.0
2016-02-25T16:43:35.363Z
I think the reason this hasn't been explored more is that it's hard to imagine what a conditional result in algorithmica would look like past what Ricky said.
Huck Bennett
<cc.complexity-theory><reference-request><np-hardness><soft-question>
Deeper look at Algorithmica?
András Salamon
# Deeper look at Algorithmica?

(Asked by: username_0 on 2016-02-17)

Russell Impagliazzo published ["A Personal View of Average-Case Complexity"](http://dx.doi.org/10.1109/SCT.1995.514853) ([preprint](http://cseweb.ucsd.edu/~russell/average.ps)) back in 1995.
He presented five possible worlds we could be living in, depending on how P and NP were related.
The first world presented is Algorithmica, in which P = NP, "or some moral equivalent" such as NP being contained in BPP, or NP = RP ≠ P.
The remaining four worlds are all variants where P ≠ NP, and they are "morally" different, with differences between the algorithmic applications of hardness differntiating the worlds.

It seems to me that there is a large landscape inside Algorithmica, and I'm wondering:

> has anyone written about Algorithmica in more detail?

The best reference I have found so far is a [blog post by Richard Lipton from 2009](https://rjlipton.wordpress.com/2009/07/03/is-pnp-an-ill-posed-problem/) which briefly explores Algorithmica but doesn't go into much detail.

---

Although it seems unlikely that we are living in Algorithmica, understanding that landscape might still motivate interesting work.
For instance, it might highlight precisely what the world would have to look like for quantum factoring to be rendered irrelevant, or if quantum factoring is ignored, where classical factoring might still be challenging.
See the related question [Status of Impagliazzo's Worlds?](https://cstheory.stackexchange.com/q/1026/109) for a discussion focused on the other parts of the landscape, including Boaz Barak's summary of a 2009 workshop about Impagliazzo's multiverse.

**Tags:** cc.complexity-theory, reference-request, np-hardness, soft-question

> **Comments:**
> **username_1**: It's funny (or maybe sad) to imagine the average STOC reviewer's response to a paper starting "Under the assumption $\mathsf{NP} \subseteq \mathsf{BPP}$, we show ...."  
> **username_2**: Let $n$ be the highest number that will ever been computed (in binary representation) by a device built by the humans; there exits a (much much smaller) busy beaver $B$ of length $b$ such that $\Sigma(b)>n$ (the busy beaver function). There exists a slightly larger machine $M$ that runs in time  $O(1)$ and on input $x$ operates as follow: simulate $B$ and if $x < \Sigma(b)$ then treat $x$ as a SAT formula and solve it using an exhaustive search, otherwise reject ... a non-constructive proof that a bunch of bits (probably less than 4242) can solve ("human") SAT in constant time :-D :-D  
> **username_3**: most researchers believe P!=NP wrt [Gasarch 2012 survey](https://www.cs.umd.edu/~gasarch/papers/poll2012.pdf). so algorithmica is regarded as unlikely. there is some consideration at length in [golden ticket](http://www.amazon.com/The-Golden-Ticket-Search-Impossible/dp/0691156492) by Fortnow, but it seems mostly speculative/ unsourced. actually this is all covered fairly well in this question [what would be the real world implications of a P=NP proof](http://cs.stackexchange.com/questions/35759/what-would-be-the-real-world-implications-of-a-constructive-p-np-proof) / [cs.se]  
> **username_2**: Joking apart, I just remembered that the whole Chapter 2 of "The Golden Ticket" by L. Fortnow is dedicated to Algorithmica: **Chapter 2 - The Beautiful World** *... To give you a tiny taste of this beautiful world, let's imagine a future world a few years after the discovery of an efficient algorithm that solves NP problems. Let's jump to the year 2026 and explore this beautiful world, almost surely a fantasy world, the world of P=NP. First let's see how this world developed ...* ... then he (informally) describes a few consequences of such discovery (e.g. medical research progress ).  
> **username_0**: Thanks for the additional pointers.  I was aware of the CS.SE question.  Trying to write a new answer to it, a map of Algorithmica was an obvious thing to already exist.  Yet I couldn't find it: hence this question.  There are many consequences of P=NP (quite possibly even every utterly false thing) but they live in several regions that are as different from each other as Algorithmica is from Impagliazzo's four other lands.  It is this structure I am interested in.  For instance, in some regions of Algorithmica the RSA cryptosystem seems perfectly viable, while in another factoring is trivial.  
> **username_1**: Not to point out the obvious, but as Yogi Berra might say, a barrier to these kinds of results is the lack of research about them. Namely, in a world of $P \neq NP$ we have a lot of work on identifying and using further assumptions, which allow the separations between the other four worlds. Before getting off the ground, research into Algorithmica might have to do the same. But it might be hard to justify or pick such assumptions if we don't think they're true....  
> **username_4**: I think the reason this hasn't been explored more is that it's hard to imagine what a conditional result in algorithmica would look like past what Ricky said.  

---

## 0 answers

