Polylog-space vs NP

Question

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). However, I'm not sure what to expect with $\text{polyL}$ relative to $\text{NP}$ and $\text{PP}$.

Note: I have read somewhere else 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.

Answer 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}$.