17
$\begingroup$

Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) 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 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? for a discussion focused on the other parts of the landscape, including Boaz Barak's summary of a 2009 workshop about Impagliazzo's multiverse.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ 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 ...." $\endgroup$
    – usul
    Feb 18, 2016 at 5:23
  • $\begingroup$ 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 $\endgroup$
    – Marzio De Biasi
    Feb 18, 2016 at 18:59
  • $\begingroup$ most researchers believe P!=NP wrt Gasarch 2012 survey. so algorithmica is regarded as unlikely. there is some consideration at length in golden ticket 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 / Computer Science $\endgroup$
    – vzn
    Feb 18, 2016 at 19:46
  • 4
    $\begingroup$ 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 ). $\endgroup$
    – Marzio De Biasi
    Feb 18, 2016 at 19:50
  • $\begingroup$ 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. $\endgroup$
    – András Salamon
    Feb 18, 2016 at 23:19

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.