<p>I wish there was a close reason for “question asks about the relation between two classes”. Nothing interesting ever comes out of these questions, yet people keep asking them over and over again. They always have the <strong>same, boring (non-)answer</strong>: classes are assumed distinct/incomparable unless there is a compelling reason to think otherwise, and there usually isn’t.</p>
<p>In 95% of the cases, the only compelling reason we might have is a <em>proof</em> that an inclusion between the classes holds: this is typically either a straightforward consequence of the definition, or it is a famous result (such as IP = PSPACE) that you can find in all the usual places (textbooks, Wikipedia, Complexity Zoo). There are only a few exceptions, such as derandomization (e.g., we expect P = BPP even though we cannot prove it yet); again, these are famous, and can be found in all the usual places. So if you do your research and come up empty-handed, you can be pretty much sure the classes are assumed distinct, or would be if you asked anyone who cared.</p>
<p>At the same time, we also hardly ever have any good <em>evidence</em> that the classes are actually distinct (and indeed, there have been a few incidents when classes were unexpectedly proved to be the same). Typically, the only cases where we <em>know</em> a noninclusion between two classes to hold is when it easily follows from a deterministic/nondeterministic time/space hierarchy theorem, possibly coupled with a padding argument. Usually you are not so lucky.</p>
<p>Sometimes, a hierarchy theorem/padding argument can be used to show that two classes are distinct, typically due to mismatch in closure properties, even though we do not know how to disprove either of the two inclusions. E.g., <span class="math-container">$\mathrm{polyL\ne NP}$</span>: if <span class="math-container">$\mathrm{NP\subseteq polyL}$</span>, then <span class="math-container">$\mathrm{NTIME}(2^{(\log n)^{O(1)}})\subseteq\mathrm{polyL}$</span> as well by a padding argument, but this class strictly contains NP by the nondeterministic time-hierarchy theorem.</p>
<p>Some assumed noninclusions are more famous than others, hence you can sometimes handwave your way into an argument that your case is sufficiently close to a famous conjecture that it should hold as well (e.g., “NP is likely not included in polyL for the same reason we believe NP is distinct from L; we actually expect that even P is not included in <span class="math-container">$\mathrm{DSPACE}(n^{o(1)})$</span>”).</p>
<p>But if at least one of your classes is obscure enough, there is often no credible supporting evidence for their noninclusion at all. Which basically makes such questions unanswerable for boring reasons. E.g., <span class="math-container">$\mathrm{polyL\nsubseteq PP}$</span> might fall in this category, though you might construe some kind of extremely shaky handwaving argument in the spirit of the previous paragraph, relating it to <span class="math-container">$\mathrm{PSPACE\nsubseteq PP}$</span>.</p>

CC BY-SA 4.0
2024-05-28T09:20:25.080Z
2024-05-28T09:25:47.920Z
2024-05-28T09:25:47.920Z
Emil Jeřábek
<p>Let <span class="math-container">$\text{polyL} = \cup_{c} \text{SPACE}[\log^c n]$</span> be the set of all problems that can be solved using polylog space, what is known/believed about its relation with NP? And perhaps even PP?</p>
<p>I'm aware that <span class="math-container">$\text{polyL}$</span> is in quasipolynomial (denoted <span class="math-container">$\text{QP}$</span>) time by a simple standard consideration of the graph of all configurations of the workspace. I suppose <span class="math-container">$\text{QP}$</span> should contain problems not in <span class="math-container">$\text{NP}$</span>. And my guess is <span class="math-container">$\text{QP}$</span> may not even be in <span class="math-container">$\text{PP} \subseteq \text{PSPACE}$</span> (I suppose is commonly believed to be <span class="math-container">$\subsetneq \text{PSPACE}$</span>, since PSPACE contains the <a href="https://complexityzoo.net/Complexity_Zoo:C#ch" rel="noreferrer">counting hierarchy</a>). However, I'm not sure what to expect with <span class="math-container">$\text{polyL}$</span> relative to <span class="math-container">$\text{NP}$</span> and <span class="math-container">$\text{PP}$</span>.</p>
<p>Note: I have read <a href="https://cstheory.stackexchange.com/questions/3439/why-do-we-consider-log-space-as-a-model-of-efficient-computation-instead-of-pol">somewhere else</a> that <span class="math-container">$\text{polyL}$</span> is not a robust class under certain robustness criteria, but I hope my question above still makes sense independent of this non-robustness.</p>

CC BY-SA 4.0
2024-05-28T07:28:12.420Z
We certainly have $\mathsf{polyL}\neq\mathsf{NP}$ and $\mathsf{polyL}\neq\mathsf{PP}$: $\mathsf{NP}$ and $\mathsf{PP}$ have complete problems under logspace reductions, $\mathsf{polyL}$ does not, because if it did, then we would get $\mathsf{polyL}=\mathsf{SPACE}(\log^c n)$ for some fixed $c$ (depending on the space complexity of the complete problem), violating the space hierarchy.  This is related to the robustness problem you hinted at (the observation itself, and some discussion about $\mathsf{polyL}$, is found somewhere in Papadimitrious's book).
Damiano Mazza
<counting-complexity><np><space-bounded><space-complexity>
Polylog-space vs NP
quantumrock
# Polylog-space vs NP

(Asked by: username_0 on 2024-05-28)

Let $\text{polyL} = \cup\_{c} \text{SPACE}[\log^c n]$ be the set of all problems that can be solved using polylog space, what is known/believed about its relation with NP? And perhaps even PP?

I'm aware that $\text{polyL}$ is in quasipolynomial (denoted $\text{QP}$) time by a simple standard consideration of the graph of all configurations of the workspace. I suppose $\text{QP}$ should contain problems not in $\text{NP}$. And my guess is $\text{QP}$ may not even be in $\text{PP} \subseteq \text{PSPACE}$ (I suppose is commonly believed to be $\subsetneq \text{PSPACE}$, since PSPACE contains the [counting hierarchy](https://complexityzoo.net/Complexity_Zoo:C#ch)). However, I'm not sure what to expect with $\text{polyL}$ relative to $\text{NP}$ and $\text{PP}$.

Note: I have read [somewhere else](https://cstheory.stackexchange.com/questions/3439/why-do-we-consider-log-space-as-a-model-of-efficient-computation-instead-of-pol) that $\text{polyL}$ is not a robust class under certain robustness criteria, but I hope my question above still makes sense independent of this non-robustness.

**Tags:** counting-complexity, np, space-bounded, space-complexity
> **Comments:**
> **username_1**: We certainly have $\mathsf{polyL}\neq\mathsf{NP}$ and $\mathsf{polyL}\neq\mathsf{PP}$: $\mathsf{NP}$ and $\mathsf{PP}$ have complete problems under logspace reductions, $\mathsf{polyL}$ does not, because if it did, then we would get $\mathsf{polyL}=\mathsf{SPACE}(\log^c n)$ for some fixed $c$ (depending on the space complexity of the complete problem), violating the space hierarchy.  This is related to the robustness problem you hinted at (the observation itself, and some discussion about $\mathsf{polyL}$, is found somewhere in Papadimitrious's book).  

---

## 1 answers

### Answer by username_2 on 2024-05-28. Score: -1

I wish there was a close reason for “question asks about the relation between two classes”. Nothing interesting ever comes out of these questions, yet people keep asking them over and over again. They always have the **same, boring (non-)answer**: classes are assumed distinct/incomparable unless there is a compelling reason to think otherwise, and there usually isn’t.

In 95% of the cases, the only compelling reason we might have is a *proof* that an inclusion between the classes holds: this is typically either a straightforward consequence of the definition, or it is a famous result (such as IP = PSPACE) that you can find in all the usual places (textbooks, Wikipedia, Complexity Zoo). There are only a few exceptions, such as derandomization (e.g., we expect P = BPP even though we cannot prove it yet); again, these are famous, and can be found in all the usual places. So if you do your research and come up empty-handed, you can be pretty much sure the classes are assumed distinct, or would be if you asked anyone who cared.

At the same time, we also hardly ever have any good *evidence* that the classes are actually distinct (and indeed, there have been a few incidents when classes were unexpectedly proved to be the same). Typically, the only cases where we *know* a noninclusion between two classes to hold is when it easily follows from a deterministic/nondeterministic time/space hierarchy theorem, possibly coupled with a padding argument. Usually you are not so lucky.

Sometimes, a hierarchy theorem/padding argument can be used to show that two classes are distinct, typically due to mismatch in closure properties, even though we do not know how to disprove either of the two inclusions. E.g., $\mathrm{polyL\ne NP}$: if $\mathrm{NP\subseteq polyL}$, then $\mathrm{NTIME}(2^{(\log n)^{O(1)}})\subseteq\mathrm{polyL}$ as well by a padding argument, but this class strictly contains NP by the nondeterministic time-hierarchy theorem.

Some assumed noninclusions are more famous than others, hence you can sometimes handwave your way into an argument that your case is sufficiently close to a famous conjecture that it should hold as well (e.g., “NP is likely not included in polyL for the same reason we believe NP is distinct from L; we actually expect that even P is not included in $\mathrm{DSPACE}(n^{o(1)})$”).

But if at least one of your classes is obscure enough, there is often no credible supporting evidence for their noninclusion at all. Which basically makes such questions unanswerable for boring reasons. E.g., $\mathrm{polyL\nsubseteq PP}$ might fall in this category, though you might construe some kind of extremely shaky handwaving argument in the spirit of the previous paragraph, relating it to $\mathrm{PSPACE\nsubseteq PP}$.


---

