1
$\begingroup$

I wonder whether there is a known relativization barrier against proving $LogCFL\neq PSPACE$. Hence I'm looking for a language $A$ for which $LogCFL^A=PSPACE^A$.

One could try $A:=TQBF$, where $TQBF$ is the $PSPACE$-complete problem to decide true quantified Boolean formulas. But relativising space-bounded classes is a very tricky business, as Emil Jeřábek tried to explain to me.

Maybe it is easier to look at the problem from the other side: Both $NL\neq PSPACE$ and $CFL\neq PSPACE$ are known. I heard multiple times that one "usually considers LOGCFL instead of CFL, since it has nicer closure properties". So maybe $LogCFL\neq PSPACE$ is known. I noticed that the German wikipedia article on NP claims that $LogCFL\neq PSPACE$ would be known, but I couldn't verify this. But if this should be known indeed, then I wonder whether it also applies to $AC^1$, or whether $LogCFL$ is really the current limit where separation from $PSPACE$ can still be proven.

$\endgroup$
1
$\begingroup$

Maybe it is easier to look at the problem from the other side: ... the German wikipedia article on NP claims that $LogCFL\neq PSPACE$ would be known, ...

It is know: $CFL \subset DSPACE(O(\log^2 n))$ was shown in [ 1 ] and "generalized" in [ 2 ] (whatever that means, I don't have full text access to those articles). This algorithm takes superpolynomial time, i.e. it is different from the CYK algorithm taught in Hopcroft and Ullman (and not even mentioned there, despite contrary claims). It directly follows that $LogCFL\subset DSPACE(O(\log^2 n))$ and hence $LogCFL \neq PSPACE$.

But if this should be known indeed, then I wonder whether it also applies to $AC^1$, ...

The English wikipedia article on complexity classes claims that $NC\neq PSPACE$ would be known. Since $AC^1\subset NC$, this would mean that it also applies to $AC^1$. This separation can be deduced from $NC^k\subset DSPACE(O(\log^k n))$, see for example Lemma 5.4 A circuit of depth $D$ can be simulated in $O(D)$ space or slides 25-28 of this ppt. So it is well known indeed.

But does this resolve the initial question whether there is a relativization barrier?

Who cares!


1 Lewis, P.M. II, R. E. Stearns, and J. Hartmanis. "Memory Bounds for the Recognition of Context-Free and Context Sensitive Languages." IEEE Conference Record on 1965 Symposium on Switching Circuit Theory and Logical Design.

2 Stephen A. Cook, Path systems and language recognition, Proceedings of the second annual ACM symposium on Theory of computing, p.70-72, May 04-06, 1970, Northampton, Massachusetts, United States

$\endgroup$
  • $\begingroup$ I do not agree that you have answered your question, but as you have answered well, it is valid. $\endgroup$ – user53451 Jun 8 '17 at 16:06
  • $\begingroup$ @PauloOliveira Well, when asking this question, I already guessed that things would turn out to be both trivial and messy. At the moment, I just cannot master the concentration necessary for that relativization barrier part of the question. And if I did, I would answer the question about Baker-Gill-Solovay oracle linked by Who cares! instead. By the way, your user profile ...???..., but your global profile works. $\endgroup$ – Thomas Klimpel Jun 8 '17 at 22:20

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.