<p>This is a favorite question of mine.</p>

<p>Fortnow showed, in his paper <a href="http://people.cs.uchicago.edu/~fortnow/papers/npvsnl.pdf">"Time-Space Tradeoffs for Satisfiability"</a>, 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. </p>

<p>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.)</p>

<p>It is open whether $NL = P^{\#P}$. The last time I seriously attempted to prove this, it resulted in the paper <a href="http://www.cs.cmu.edu/~ryanw/mod-lbs-full3.pdf">"Time-Space Tradeoffs for Counting NP Solutions Modulo Integers"</a>. 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.</p>

<p>Uniform-$TC^0$ is properly contained in $P^{\#P}$. The proof is in Allender, <a href="http://ftp.cs.rutgers.edu/pub/allender/threshold.pdf">"The Permanent Requires Large Uniform Threshold Circuits"</a>. 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.)</p>

CC BY-SA 3.0
2014-08-29T03:44:15.517Z
Cool! (BTW, regarding your last non-parenthetical sentence: Koiran and Perifel http://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
CC BY-SA 3.0
2014-08-29T06:02:34.777Z
Yeah, I know about that one too, and other references as well. But I kept to a summary answer that wouldn't take more than 10 minutes to write.
Ryan Williams
CC BY-SA 3.0
2014-08-28T22:32:06.070Z
2014-08-28T22:32:06.070Z
Ryan Williams
<p>The wikipedia page on PSPACE mentions that the inclusion $NL\subset PH$ is not known to be strict (unfortunately without references). </p>

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

<p>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?</p>

<p>Q3: Are such inclusions discussed in literature?</p>

CC BY-SA 3.0
2014-08-28T00:31:50.790Z
I guess for Q2 you mean strictly contained in PSPACE?
Sasho Nikolov
CC BY-SA 3.0
2014-08-28T04:24:26.773Z
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
CC BY-SA 3.0
2014-08-28T04:51:18.360Z
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
CC BY-SA 3.0
2014-08-28T07:32:34.507Z
Your question title says "Largest class". Don't you mean "smallest class"?
Shaull
CC BY-SA 3.0
2014-08-28T10:11:30.417Z
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
CC BY-SA 3.0
2014-08-28T13:48:32.380Z
Sasho: in principle I'm also interested in classes which aren't contained in PSPACE, Shaull: I really meant largest, but I changed the title slightly so that it woudn't suggest that I'm itnerestend in some unique class
Łukasz Grabowski
<cc.complexity-theory><complexity-classes><logspace>
Large classes which contain LOGSPACE for which strict inclusions are unknown
Łukasz Grabowski
# Large classes which contain LOGSPACE for which strict inclusions are unknown

(Asked by: username_0 on 2014-08-27)

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?

**Tags:** cc.complexity-theory, complexity-classes, logspace
> **Comments:**
> **username_1**: I guess for Q2 you mean strictly contained in PSPACE?  
> **username_2**: 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.)  
> **username_3**: 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.  
> **username_4**: Your question title says "Largest class". Don't you mean "smallest class"?  
> **username_5**: 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.  
> **username_0**: Sasho: in principle I'm also interested in classes which aren't contained in PSPACE, Shaull: I really meant largest, but I changed the title slightly so that it woudn't suggest that I'm itnerestend in some unique class  

---

## 1 answers

### Answer by username_6 on 2014-08-28. Score: 8

This is a favorite question of mine.

Fortnow showed, in his paper ["Time-Space Tradeoffs for Satisfiability"](http://people.cs.uchicago.edu/~fortnow/papers/npvsnl.pdf), 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"](http://www.cs.cmu.edu/~ryanw/mod-lbs-full3.pdf). 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"](http://ftp.cs.rutgers.edu/pub/allender/threshold.pdf). 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.)

> **Comments:**
> **username_3**: Cool! (BTW, regarding your last non-parenthetical sentence: Koiran and Perifel http://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.)  
> **username_6**: Yeah, I know about that one too, and other references as well. But I kept to a summary answer that wouldn't take more than 10 minutes to write.  

---

