Make Your Own World
What would you do if you could do anything?
Ian Munro is a world expert on data structures and algorithms—I have discussed some of his great results previously here.
Today Ken and I wish to examine a fantasy world where you can shape the answers to the questions: is equal to ?, is equal to co-?, is equal to ?, and so on.
Munro has a wonderful sense of humor; it has always been a delight to work with him. One of his crazy ideas was: what makes a problem -complete? In the early seventies one of the main types of papers were those that had theorems of the form:
Theorem: It is -complete to determine whether an has property .
Program committees started to tire of such results, so eventually only really hard theorems of this kind were accepted, and finally almost no such papers were accepted. One, of the few, that was accepted, in FOCS 1996, is a beautiful result due to Michael Rabin:
Theorem: Computing the number of zeroes modulo a prime of a linear recurrence sequence over is an -hard problem.
Note, because the values of the recurrence are from a finite set, , this makes sense: there only are a finite number of values.
Nevertheless, these papers have never seemed to yield a simple answer to Munro’s question: can we identify a property of the problem that makes it -complete? It is true that all known -complete sets are polynomial-time isomorphic, so in a sense is the same for all these problems. But that doesn’t give us a meta-method for looking at a concrete given problem and telling that it’s -complete, which would have simplified the issue of all these papers.
A Fantasy World
Munro’s feeling on the lack of simple ‘s led him to speculate that complexity gives a convincing illusion that mathematical truth is participatory. He told me that every problem is either complete or in —well most problems. If the first researcher who worked on the problem tried to show that it was hard, then it became -complete; if the first tried to find an algorithm, then it was found to be in . A strange, but cool, theory.
Let’s modify Ian’s world just a bit: Complexity is so participatory that you can just decide what answers you want for all of the open questions. You can design your own world: what would you do? Would you make all the classes that we think are different, different? Or would you collapse lots of classes? Here are two different views from Ken and myself.
I, Ken, would make the choices that maximize the need for a creative response by humanity. With regard to Russell Impagliazzo’s Five Worlds, I take this to be “Cryptomania.” This means not only , but also that public-key cryptography is possible, with security in a heavy preponderance of cases. However, this would not come via the hardness of Factoring, but by dint of elliptic curves or polynomial ideal theory.
The polynomial hierarchy would be distinct as far as , but I find it plausible to make it collapse at level three: closed under complement. Also , but I guess I would design . I could go into further detail about how succinctness and computational depth play into the hardness of problems, but suffice it now to say that enough should be solvable to “get by with a little help from our friends.” Beyond that, per ardua ad astra—to the stars through struggle.
For recent news on Impagliazzo’s Worlds, see this.
I, Dick, would make the choices that maximize the need for a creative response by humanity. I would make equal to . How can I claim that this would “maximize the need for a creative response,” as Ken’s also would? I will explain.
In this world complexity theory would be immensely simpler. The famous Complexity Zoo would suddenly discover that many of the “animals” they carefully keep in different “cages,” were actually exactly the same. Cryptography would be in big trouble, quantum computing would be gone, and the upheaval would be gigantic.
This unexpected collapse, would generally cause a huge upheaval—famous results would be gone, for example. The collapse would require new deep ideas: how could we make security work? Possibly we would have to turn to physical assumptions? Perhaps we would have to use space limitations or other approaches to security.
What would you do?