A hole in the web
The sun rose this morning on a radically transformed blogosphere: sparser, emptier, populated by only one Cornell-educated prover of complexity class inclusions and oracle separations from the Northeast US.
To everyone in the CS theory community, I want you to know that I’m acutely aware of the central role that Lance’s weblog played for all of us; and the burden of somehow filling the void he left now weighs heavily on me. To that end, I’d like to offer you the following sneak preview of upcoming topics on Shtetl-Optimized.
- Paper vs. Electronic Proceedings: The Debate Continues
- Ordering of Authors: Who Should Go Third?
- Greatest Hits of the 60’s and 70’s: Why Can One-Tape Turing Machines Polynomially Simulate Multitape Turing Machines?
- Complexity Class of the Week:
- Baseball and Complexity: They Might Not Seem Related, But They Are
- Giving “The Man” His Due: Why We Should All Support Bush, Diebold, and Elsevier
Oh, who am I kidding? I can’t speak for the Establishment the way Lance could! Having me serve as a clearinghouse for the theory community would be putting one of the very worst-behaved inmates in charge of the asylum.
So maybe I should just stick to biting vagina jokes.
OK, I will. Without further ado, here’s an article sent to me by my good friend Sharon Haiduck, about a South African company that’s finally accomplished what a billion years of natural selection couldn’t.
Follow
Comment #1 March 26th, 2007 at 5:39 pm
what the hell is up with QMA? is there any reason to believe it can do more than NP?
Comment #2 March 26th, 2007 at 5:46 pm
Yes, there is. Firstly, if BQP⊄NP, then certainly QMA⊄NP as well. Secondly, we do have some interesting problems in QMA that are not known to be in NP, such as Babai’s Group Non-Membership problem. See this paper by John Watrous, or this one by myself and Greg Kuperberg.
Comment #3 March 26th, 2007 at 6:15 pm
Well, with an oracle, GNM is known not to be in NP; but without an oracle, it is reasonable to conjecture that it is in NP. Even so, GNM uses a reasonable-looking oracle that only hides group structure. It is not like the oracle that separates BPP from NP. That oracle is a conspiracy that hides an obvious statistical truth from deterministic verifiers.
I believe that strong evidence will appear that QMA is bigger than NP. For one thing, Scott and I found a quantum oracle that separates QMA from QCMA, and QCMA contains NP. Now, that is not entirely fair because NP can’t read quantum oracle at all, but even so, I think that our paper points in the right direction. In the meantime, one good question to consider is whether there is an oracle that separates BQP from AM. When there is no oracle, people believe that AM = NP. Finding an oracle that separates BQP from AM is central to the question of whether BQP is in NP. Again, you can use a conspiracy oracle to separate BQP and even BPP from NP, but that says very little about the empty oracle. AM is a better comparison because AM is good at unearthing conspiracies hidden in oracles.
I would bet 100 to 1 that QMA is bigger than NP; maybe 20 to 1 that it is bigger than QCMA and QCAM. I would also bet 100 to 1 that BQP is bigger than P or BPP. But I would only bet 4 to 1 that BQP is not in NP, unrelativized.
Comment #4 March 26th, 2007 at 6:36 pm
That’s all cool, but it turns out that I had the name wrong.
What I really care about (for the limited purpose at hand) is QCMA… so, what’s your odds on that versus NP?
Comment #5 March 26th, 2007 at 6:37 pm
(Thanks for all the help and the link to Dorit’s survey.)
Comment #6 March 26th, 2007 at 6:43 pm
Alright, I’ll give you 10:1 odds that QCMA⊄NP unrelativized. (We certainly know an oracle that separates them, namely the “conspiracy oracle” relative to which BQP⊄NP. But as Greg discussed, that doesn’t necessarily tell us much.)
Greg, do you feel similarly? (For all of the questions you mentioned, your odds are remarkably similar to mine.)
Comment #7 March 26th, 2007 at 8:18 pm
I said 4:1 for BQP⊄NP, so I might say 5:1 for QCMA⊄NP, unrelativized. If Merlin makes a classical Arthur as smart as a quantum Arthur, then I don’t see why a classical proof would help the quantum Arthur much. In fact, I note the folllowing: If BQP⊂NP, then automatically ∃BQP⊂NP by class operators. Suppose that only slightly more were true, that qP (as I discussed it in another post) were contained in fuzzy MA. Then a class operator argument would tell you that QCMA = MA.
Quantum proofs, on the other hand, are really powerful. I have an incentive to think so: it makes our paper look good. 🙂
We certainly know an oracle that separates them, namely the “conspiracy oracle” relative to which BQP⊄NP. But as Greg discussed, that doesn’t necessarily tell us much.
Actually, although we didn’t explicitly note this, I think that our paper shows that a GNM-type oracle, which is much more reasonable oracle than conspiracies against determinism, separates QCMA from MA. Isn’t abelian GNM already not in MA?
Comment #8 March 26th, 2007 at 8:21 pm
Sorry, I shouldn’t even credit our paper for the abelian case. Abelian GNM is in BQP by Shor-Kitaev.
Comment #9 March 28th, 2007 at 8:19 am
Just as an aside, Greg, about that earlier post concerning qP and similar classes: is this a subject of fuzzy computational theory? If so, is there something you would recommend as a good introduction to the subject?
I’m envisioning these complexity classes as perhaps representing (sharp) sets of (sharp) uniform families of fuzzy-valued functions — e.g. “decision” of membership to a fuzzy set for decision problems — where the uniformity is a constraint on the parameters describing the fuzziness of the outputs. Or, perhaps, (sharp) sets of fuzzy uniform families of fuzzy-valued functions, where the fuzziness of the uniform families corresponds to the ability to uniformly approximate the fuzziness of the functions.
Comment #10 March 28th, 2007 at 9:07 am
“Fuzzy” is just my shorthand for a complexity class for which the outputs are probability distributions. The virtue of this term is that “fuzzy” has two syllables, while “probabilistic” has five.
Complexity classes with probabilistic output would tame a mess that has developed in the art of organizing complexity classes. The mess involves both class operators (for instance, the spurious difference between ∃BPP and MA) and class exponentiation (for instance, that UP^RP is a spurious class that resembles but does no equal the one in the Valiant-Vazirani theorem). Scott suggested using promise classes to clean up this mess. I am convinced that fuzzy classes in my sense are the best solution. However, my suggestion has not really been developed in a textbook or research paper. Moreover, there there has been a general trend in theoretical CS away from defining and relating complexity classes and towards other models of hardness and easiness.
That said, fuzzy means slightly different things in different contexts, and it is possible that someone else has developed a theory of fuzzy complexity classes for some other purpose.
Comment #11 March 28th, 2007 at 10:36 am
“Complexity Class of the Week: ”
LOL!!! 😀 😀
Comment #12 March 28th, 2007 at 10:37 am
huh… the image didn’t appear, but you get the idea
Comment #13 March 28th, 2007 at 1:59 pm
Osias Says: Complexity Class of the Week … LOL! 😀 😀
Hey, that’s the one topic that I thought was serious! Because the Molecule of the Month (MOTM) web site is quite famous, you know. And surely, the number of complexity classes is similar to the number of biological molecules. After all, both are evolved structures.
Or am I missing something? 🙂
Comment #14 March 28th, 2007 at 2:07 pm
similar?!?