# Polylog-space vs NP

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.

• 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). Commented May 28 at 7:28

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