12
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I guess for Q2 you mean strictly contained in PSPACE? $\endgroup$ – Sasho Nikolov Aug 28 '14 at 0:31
  • 5
    $\begingroup$ 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.) $\endgroup$ – Kaveh Aug 28 '14 at 4:24
  • 4
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Aug 28 '14 at 4:51
  • $\begingroup$ Your question title says "Largest class". Don't you mean "smallest class"? $\endgroup$ – Shaull Aug 28 '14 at 7:32
  • 4
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek supports Monica Aug 28 '14 at 10:11
7
$\begingroup$

This is a favorite question of mine.

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

$\endgroup$
  • 3
    $\begingroup$ 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.) $\endgroup$ – Joshua Grochow Aug 29 '14 at 3:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Ryan Williams Aug 29 '14 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.