Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top