Life in Algorithmica

In 2009, the Center for Computational Intractability organized a workshop on the status of “Impagliazzo’s Worlds,” which are possible resolutions of the P=NP question that have different implications for cryptography.  Russell Impagliazzo gave the first talk, with the following abstract:

“A personal view on average-case complexity” introduced five possible worlds as metaphors for the outcomes of fundamental questions in complexity concerning whether and to what extent intractable problems exist.  In this talk, I will try to put forward some concrete open problems addressing these issues.  I will emphasize those problems I believe are within reach, in that there is no fundamental reason they should be difficult, but whose solutions would cast light on which of the five worlds is the case and what these worlds look like.

A video of this talk is here, and I watched it recently.  Most surprising to me, perhaps, was how many open questions there are even if we live in Algorithmica, the world where P=NP.  I will summarize this section of Impagliazzo’s talk in the rest of this post.

First off, Algorithmica isn’t really the world where P=NP; it is the world where NP-complete problems are easy — a much stronger condition.  In such a world, we only need one fast search/optimization algorithm to solve any of the thousands of NP-complete problems.  Practical applications reduce to figuring out the appropriate set of constraints to use to express the problem of interest in the “language” of Satisfiability.  Further, mathematics — and anything else humans can do — could be completely automated, because we could train a computer to do whatever we want, even if we don’t know how to express precisely what we want.  For example, it is possible for a computer to learn to simulate a person so closely it is impossible to tell the difference.  Just have the computer say something, and say, “Yes, that sounds like person X,” or, “No, that doesn’t.”  Very quickly, the computer will learn to imitate person X.

Formally, the achievement of undetectable simulation is possible, because “learning” is in the polynomial hierarchy (PH), and, if P=NP, the polynomial hierarchy collapses, meaning nothing in PH is harder than NP, and we already know that NP is easy.  More about the polynomial hierarchy below.

Of course, in a world of no verifiable identity, there is no way to guarantee computer security.  You never know if you are talking to a person or a simulation.  However, even in such a dramatic world, there are questions we don’t know the answer to.  In particular:

Could computers in Algorithmica simulate quantum interactions?

Formally, does it follow that \mathsf{P} = \mathsf{NP} \Rightarrow \mathsf{P} = \mathsf{BQP}?  In other words, would it still be worthwhile to build a quantum computer?

We can also consider a weakening (or is it really a weakening?) of Algorithmica, which Impagliazzo termed qAlgorithmica.  This is a world where NP-complete problems can be solved efficiently, but we need quantum computers to solve them.  (Formally, \mathsf{NP} \subseteq \mathsf{BQP}.)  As before, we still need only one search/optimization algorithm, but it is not clear that all the dramatic/frightening consequences of full Algorithmica still hold, because the polynomial hierarchy may not collapse.  The open problem then becomes, if we can solve NP-complete problems quickly with quantum computers, how much of full Algorithmica is in effect? (Formally, does the implication \mathsf{NP} \subseteq \mathsf{BQP} \Rightarrow \mathsf{PH} \subseteq \mathsf{BQP} hold?)

Finally, we can try to formalize the question, If NP-complete problems are easy, how much else is easy? (Probably \mathsf{P} \neq \mathsf{NP} so everything is easy if P=NP, but let’s play along for a moment.)  Impagliazzo presented a notion due to Ken Regan, the class of languages \mathsf{H} defined as:

\mathsf{H} = \{ \mathcal{L} \mid \forall \mathrm{A} [\mathsf{P}^{\mathrm{A}} = \mathsf{NP}^{\mathrm{A}} \rightarrow \mathcal{L} \in \mathsf{P}^\mathrm{A}] \}

where \mathcal{L} is a language over, e.g., \{0,1 \}^*.  The polynomial hierarchy is contained in \mathsf{H}, but \mathsf{H} can’t be too much bigger than PH, because it can be shown that H is contained in log log-many quantifier alternations.  (Log log is intentional, not a typo.)  In particular, \mathsf{H} is contained in a counting class that, as far as we currently know, contains nothing outside the polynomial hierarchy.  So, for all we know, \mathsf{H} and \mathsf{PH} are the same.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s