3
$\begingroup$

Having read some chapters of Computational Complexity: A Modern Approach, I see no time or space hierarchy theorem which applies to this case. As far as I can see, we know the following inclusions:

$L \subseteq NL \subseteq P \subseteq BPP \subseteq BQP \subseteq QMA$

but no inclusion is known to be strict, and it is not known whether at least one of these inclusions is strict. The statements $L=P, P=BQP, BQP=QMA$ are all unsolved, so I am free to conjecture that they are all true, or all false. I know that it is absolutely obvious that $L\subsetneq QMA$, because to go from one to the other one must (1) remove the logarithmic space bound, (2) introduce randomness to the algorithm, (3) add quantum and (4) add nondeterminism. This question is interesting because each of these augmentations is believed but not proved to add computational power (with the possible exception of (2)), they correspond to their respective flagship inclusions above, and this question captures all of them simultaneously, showcasing an enormously long distance unsolved relationship. It is also interesting because to my knowledge it is the longest-distance unresolved inclusion between two natural complexity classes (classes that arise naturally in studying theory and which capture fundamental notions of resource-bounded computation, but this point is subjective).

The only strict inclusions I can find are $L\subsetneq Space(n) \not= NP$ and $L \subsetneq PSPACE \supseteq P$. The first is not satisfying because $Space(n) \subsetneq NP$ is open.

This also begs the question, alright if these augmentations individually are hard to reason about, but surely you cannot add them all at once without changing your complexity class? And is it easier to prove such weaker strict inclusions?

(and, tongue in cheek, if the answer to my question is yes, what have complexity theorists been up to the past few decades?)

$\endgroup$
  • $\begingroup$ I'm a bit confused. I appreciate the context and background, but at the end of the day, what is your specific question? (Note that the site works best if you ask only one question per post.) $\endgroup$ – D.W. Apr 30 '16 at 2:12
  • $\begingroup$ I'm under the impression that (2) is usually believed to not "add computational power". ​ ​ $\endgroup$ – user12859 Apr 30 '16 at 2:36
  • $\begingroup$ @D.W. My specific question is whether $L\subsetneq QMA$ is a known result. The other questions are added as food for thought and as motivation and would be answered if $L\subsetneq QMA$ were proved. $\endgroup$ – Lieuwe Vinkhuijzen Apr 30 '16 at 9:08
  • $\begingroup$ @RickyDemer That's true, in the sense that we conjecture that algorithms can be derandomized, but we know that interactive proofs cannot. The conjecture is still relevant, because interactive proofs are not within the scope of my question. $\endgroup$ – Lieuwe Vinkhuijzen Apr 30 '16 at 9:30
  • $\begingroup$ The Space Hierarchy Theorem gives better strict inclusions for L. ​ ​ $\endgroup$ – user12859 May 2 '16 at 15:11
1
$\begingroup$

Widely open, I can tell. $\mathrm{QMA}\subseteq\mathrm{PP}$ is known. But, $\mathrm{PP}$ has been only separated from $\mathrm{uniform}$-$\mathrm{TC}^0$ up to now. So, even the stronger claim $\mathrm{L}=\mathrm{PP}$ is still unrefutable.

From the Wikipedia article https://en.wikipedia.org/wiki/PP_(complexity)#PP_compared_to_other_complexity_classes, $\mathrm{PP}$ strictly contains $\mathrm{TC}^0$, the class of constant-depth, unbounded-fan-in uniform boolean circuits with majority gates. (Allender 1996, as cited in Burtschick 1999)

Allender, E. (1996). "A note on uniform circuit lower bounds for the counting hierarchy". Proceedings 2nd International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science. 1090. Springer-Verlag. pp. 127–135

Burtschick, Hans-Jörg; Vollmer, Heribert (1999). "Lindström Quantifiers and Leaf Language Definability". ECCC TR96-005

$\endgroup$
  • $\begingroup$ Thank you for your answer! It would be great if you could provide a reference for the separation PP != Uniform TC0. In fact, I think even the stronger claim $L=CH$ is unknown. (indeed, $L=PP\iff L=CH$, isn't it?) $\endgroup$ – Lieuwe Vinkhuijzen Sep 8 '18 at 9:31
  • $\begingroup$ The circuit lowerbound's paper is added. And yes, $\mathrm{L}=\mathrm{PP} \iff \mathrm{L}=\mathrm{CH}$, using the definition of $\mathrm{CH}= \mathrm{PP} \cup \mathrm{PP}^\mathrm{PP}\cup\dots$ $\endgroup$ – user92914 Sep 8 '18 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.