# Large classes which contain LOGSPACE for which strict inclusions are unknown

The wikipedia page on PSPACE mentions that the inclusion $NL\subset PH$ is not known to be strict (unfortunately without references).

Q1: What about $L\subset PH$ and $L\subset P^{\#P}$ - are these known to be strict?

Q2: If no, is there an established class $C$ which contains $P^{\#P}$ and for which it is not known if the inclusion $L\subset C$ is strict?

Q3: Are such inclusions discussed in literature?

• I guess for Q2 you mean strictly contained in PSPACE? – Sasho Nikolov Aug 28 '14 at 0:31
• AFAIK, the only know separation for $\mathsf{L}$ is the space hierarchy theorem. I don't think it is known if any of classes mentioned in the question can simulate super-logarithmic space so they are also not known to be strict. (Not knowing a separation is not a result so that is probably the reason there are no references.) – Kaveh Aug 28 '14 at 4:24
• Even for smaller classes than $\mathsf{L}$, such as uniform $\mathsf{NC}^1$, the inclusions of Q1 are not known to be strict. I think, given the current state of knowledge, essentially any class $C$ between $\mathsf{P}^{\mathsf{\# P}}$ and strictly contained in $\mathsf{PSPACE}$ is a positive answer to Q2. – Joshua Grochow Aug 28 '14 at 4:51
• Your question title says "Largest class". Don't you mean "smallest class"? – Shaull Aug 28 '14 at 7:32
• It's not even known whether $AC^0[6]$ is strictly included in PH. $P^{\#P}$ strictly contains TC^0 by a hierarchy argument, but as Joshua Grochow already mentioned, this is not known for NC^1. For Q2, you can take CH. – Emil Jeřábek Aug 28 '14 at 10:11

Fortnow showed, in his paper "Time-Space Tradeoffs for Satisfiability", that $NL$ is properly contained in $\Sigma_{a(n)} P$, where $a(n)$ is any unbounded function. That is, nondeterministic logspace is properly contained in alternating polynomial time with $a(n)$ alternations.
Showing that $NL$ is not in $\Sigma_k P$ for a fixed constant $k$ would imply that $NL \neq NP$. (To see this, consider the contrapositive.)
It is open whether $NL = P^{\#P}$. The last time I seriously attempted to prove this, it resulted in the paper "Time-Space Tradeoffs for Counting NP Solutions Modulo Integers". I was trying to find some simulation of every language in logspace that would take $n^k$ time for some fixed $k$ when one has access to an oracle for counting satisfying assignments to a given formula. (This would imply $LOGSPACE \neq P^{\#P}$.) My approach didn't work, but I ended up using the same approach to prove time-space lower bounds for solving $Mod_6 SAT$ and other related results.
Uniform-$TC^0$ is properly contained in $P^{\#P}$. The proof is in Allender, "The Permanent Requires Large Uniform Threshold Circuits". Any improvement on this separation is open. (For example, proving uniform-$NC^1 \neq P^{\#P}$ is open, and proving uniform-$TC^0 \neq NP$ is also open.)
• Cool! (BTW, regarding your last non-parenthetical sentence: Koiran and Perifel arxiv.org/abs/0902.1866 improved Allender's result to poly-size uniform $\mathsf{TC}$ circuits of depth $o(\log \log n)$ - but I think any improvement on that is open.) – Joshua Grochow Aug 29 '14 at 3:44