<blockquote>
  <p>My question is just whether there is a known relativization barrier.</p>
</blockquote>

<p>Yes, there is a known relativization barrier. It's given by $A:=TQBF$, because Emil Jeřábek (see comments) is right: the statement that $TQBF$ is $PSPACE$-complete under logspace many-one reductions is <a href="http://www.cs.berkeley.edu/~luca/cs172-07/solutions/sol10.pdf" rel="nofollow">well</a> <a href="https://cseweb.ucsd.edu/classes/sp13/cse200-a/handouts/lec-08-0424.pdf" rel="nofollow">known</a>.</p>

<hr>

<p>Emil Jeřábek's remark "(or even uniform $\mathbf{AC}^0$)" seems less relevant, because $\mathbf{AC}^0$ is easily separated from $L$ (or even uniform $\mathbf{NC}^1$). Because the resulting formula actually depends only very locally on the input for the $PSPACE$-Turing machine, one could even claim that $TQBF$ is $PSPACE$-complete under $L$-uniform $\mathbf{NC}^0$ (instead of <a href="http://people.cs.umass.edu/~immerman/pub/bis.pdf" rel="nofollow">uniform</a> $\mathbf{AC}^0$). But I find this misleading, because the circuit doesn't really do any non-trivial work at all, it basically just writes down a template.</p>

<p>(The reduction writes down $n^k$ times $\exists c_{1.5}\forall (c_3, c_4) \in \{(c_1, c_{1.5}), (c_{1.5}, c_2)\}$ with systematically varying indices, where each $c_i$ are actually $n^k$ Boolean variables. This entire part only depends on the length of the input, hence the corresponding output variables are hardwired to constants. The final formula could be written as $\forall z. (z_1=i_i\land\dots\land z_n=i_n)\land \phi(x,y,z)$ such that only $i_i,\dots,i_n$ depends on the actual input, and such that this is the only place where $i_i,\dots,i_n$ appear. So this is nearly trivially an $\mathbf{NC}^0$, the entire work has been done by the $L$-algorithm writing down the circuit, whose outputs are nearly all directly hardwired to constant.)</p>

CC BY-SA 3.0
2015-05-21T22:38:59.513Z
It's a bit embarrassing to ask a question with such a trivial well known answer. However, compared to actually spending time trying to separate $L$ from $P$ by simple approaches like looking at the $P$-complete Horn-SAT problem, it makes sense to first ask whether there are known mathematical reasons why we expect that separating $L$ from $NP$ will be difficult.
Thomas Klimpel
CC BY-SA 3.0
2015-05-21T22:38:52.180Z
2015-05-21T22:48:29.700Z
2015-05-21T22:48:29.700Z
Thomas Klimpel
<p>I wonder<sup>1</sup> whether there is a known relativization barrier against proving $L\neq NP$. Hence I'm looking for a language $A$ for which $L^A=NP^A$.</p>

<p>My first idea was to try $A:=SAT$, but then I thought that $L^A\subset P^A = \Delta_2^P$ and $NP^A=\Sigma_2^P$. This seems to disqualify not only $A:=SAT$, but any complete problem $A$ from the <a href="http://en.wikipedia.org/wiki/Polynomial_hierarchy" rel="nofollow noreferrer">polynomial hierarchy</a> for my purpose.</p>

<p>My next idea was to try $A:=TQBF$, where $TQBF$ is the $PSPACE$-complete problem to decide <a href="http://en.wikipedia.org/wiki/True_quantified_Boolean_formula" rel="nofollow noreferrer">true quantified Boolean formulas</a>. But $P^A=NP^A$ is well known, and $L^A=NP^A$ is a stronger statement, so $L^A=NP^A$ would be well known, if anybody had proved it.</p>

<blockquote>
  <p>My question is just whether there is a known relativization barrier. We certainly can't prove that such a language $A$ can't exist, because otherwise we would get $L\neq NP$ as corollary.</p>
</blockquote>

<hr>

<p><sub>
 1. I <a href="https://cs.stackexchange.com/a/42306">know</a> that logarithmically space bounded TMs with stack recognize exactly the languages from $P$, independent of whether the TM is deterministic or not. I don't know whether this result relativizes, but I guess it does. So I wonder whether there can be a language $A$ with $NL^A=P^A$. But asking for $L^A=NP^A$ instead seems easier, because of the connection to the polynomial hierarchy.
</sub></p>

CC BY-SA 3.0
2015-05-14T13:39:53.497Z
I can’t say I quite understand the question, but TQBF is PSPACE-complete under logspace (or even uniform $\mathrm{AC}^0$) many-one reductions, hence $\mathrm{L^{TQBF}}=\mathrm{PSPACE}=\mathrm{NP^{TQBF}}$.
Emil Jeřábek
CC BY-SA 3.0
2015-05-14T14:13:14.710Z
@EmilJeřábek Are you sure? I think $PSPACE^{TQBF}=PSPACE$ (of course I may be wrong), so $L^{TQBF}=PSPACE$ would imply $L^{TQBF}=PSPACE^{TQBF}$. I think that the space hierarchy theorem relativizes, so $L^{TQBF}=PSPACE^{TQBF}$ should contradict the space hierarchy theorem.
Thomas Klimpel
CC BY-SA 3.0
2015-05-14T14:26:34.590Z
Relativizing space-bounded classes is a very tricky business, and there are multiple definitions used in different contexts, but not differentiated in notation. The definition of $\mathrm{PSPACE^{TQBF}}$ that makes it equal to PSPACE (and to $\mathrm{NP^{TQBF}}$, for that matter) is one where the oracle queries are restricted to polynomial length. The definition of $\mathrm{PSPACE^{TQBF}}$ for which you could relativize the space-hierarchy theorem to obtain $\mathrm{L^{TQBF}}\subsetneq\mathrm{PSPACE^{TQBF}}$ is one where oracle queries are unrestricted, and thus potentially exponentially long.
Emil Jeřábek
CC BY-SA 3.0
2015-05-14T14:44:04.193Z
@EmilJeřábek I see. Both $L$ and $NP$ can only make oracle queries of polynomial length, even if we allow them to try to make longer queries. So your first comment should answer my question, if the statement that $TQBF$ is $PSPACE$-complete under logspace many-one reductions is well known.
Thomas Klimpel
<cc.complexity-theory><relativization>
Relativized world where $L^A=NP^A$
Thomas Klimpel
# Relativized world where $L^A=NP^A$

(Asked by: username_0 on 2015-05-14)

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

My first idea was to try $A:=SAT$, but then I thought that $L^A\subset P^A = \Delta\_2^P$ and $NP^A=\Sigma\_2^P$. This seems to disqualify not only $A:=SAT$, but any complete problem $A$ from the [polynomial hierarchy](http://en.wikipedia.org/wiki/Polynomial_hierarchy) for my purpose.

My next idea was to try $A:=TQBF$, where $TQBF$ is the $PSPACE$-complete problem to decide [true quantified Boolean formulas](http://en.wikipedia.org/wiki/True_quantified_Boolean_formula). But $P^A=NP^A$ is well known, and $L^A=NP^A$ is a stronger statement, so $L^A=NP^A$ would be well known, if anybody had proved it.

> My question is just whether there is a known relativization barrier. We certainly can't prove that such a language $A$ can't exist, because otherwise we would get $L\neq NP$ as corollary.

---

1. I [know](https://cs.stackexchange.com/a/42306) that logarithmically space bounded TMs with stack recognize exactly the languages from $P$, independent of whether the TM is deterministic or not. I don't know whether this result relativizes, but I guess it does. So I wonder whether there can be a language $A$ with $NL^A=P^A$. But asking for $L^A=NP^A$ instead seems easier, because of the connection to the polynomial hierarchy.

**Tags:** cc.complexity-theory, relativization

> **Comments:**
> **username_1**: I can’t say I quite understand the question, but TQBF is PSPACE-complete under logspace (or even uniform $\mathrm{AC}^0$) many-one reductions, hence $\mathrm{L^{TQBF}}=\mathrm{PSPACE}=\mathrm{NP^{TQBF}}$.  
> **username_0**: @EmilJeřábek Are you sure? I think $PSPACE^{TQBF}=PSPACE$ (of course I may be wrong), so $L^{TQBF}=PSPACE$ would imply $L^{TQBF}=PSPACE^{TQBF}$. I think that the space hierarchy theorem relativizes, so $L^{TQBF}=PSPACE^{TQBF}$ should contradict the space hierarchy theorem.  
> **username_1**: Relativizing space-bounded classes is a very tricky business, and there are multiple definitions used in different contexts, but not differentiated in notation. The definition of $\mathrm{PSPACE^{TQBF}}$ that makes it equal to PSPACE (and to $\mathrm{NP^{TQBF}}$, for that matter) is one where the oracle queries are restricted to polynomial length. The definition of $\mathrm{PSPACE^{TQBF}}$ for which you could relativize the space-hierarchy theorem to obtain $\mathrm{L^{TQBF}}\subsetneq\mathrm{PSPACE^{TQBF}}$ is one where oracle queries are unrestricted, and thus potentially exponentially long.  
> **username_0**: @EmilJeřábek I see. Both $L$ and $NP$ can only make oracle queries of polynomial length, even if we allow them to try to make longer queries. So your first comment should answer my question, if the statement that $TQBF$ is $PSPACE$-complete under logspace many-one reductions is well known.  

---

## 1 answers

### Answer by username_0 on 2015-05-21. Score: 2 | Accepted answer

> My question is just whether there is a known relativization barrier.

Yes, there is a known relativization barrier. It's given by $A:=TQBF$, because username_1 (see comments) is right: the statement that $TQBF$ is $PSPACE$-complete under logspace many-one reductions is [well](http://www.cs.berkeley.edu/~luca/cs172-07/solutions/sol10.pdf) [known](https://cseweb.ucsd.edu/classes/sp13/cse200-a/handouts/lec-08-0424.pdf).

---

username_1's remark "(or even uniform $\mathbf{AC}^0$)" seems less relevant, because $\mathbf{AC}^0$ is easily separated from $L$ (or even uniform $\mathbf{NC}^1$). Because the resulting formula actually depends only very locally on the input for the $PSPACE$-Turing machine, one could even claim that $TQBF$ is $PSPACE$-complete under $L$-uniform $\mathbf{NC}^0$ (instead of [uniform](http://people.cs.umass.edu/~immerman/pub/bis.pdf) $\mathbf{AC}^0$). But I find this misleading, because the circuit doesn't really do any non-trivial work at all, it basically just writes down a template.

(The reduction writes down $n^k$ times $\exists c\_{1.5}\forall (c\_3, c\_4) \in \{(c\_1, c\_{1.5}), (c\_{1.5}, c\_2)\}$ with systematically varying indices, where each $c\_i$ are actually $n^k$ Boolean variables. This entire part only depends on the length of the input, hence the corresponding output variables are hardwired to constants. The final formula could be written as $\forall z. (z\_1=i\_i\land\dots\land z\_n=i\_n)\land \phi(x,y,z)$ such that only $i\_i,\dots,i\_n$ depends on the actual input, and such that this is the only place where $i\_i,\dots,i\_n$ appear. So this is nearly trivially an $\mathbf{NC}^0$, the entire work has been done by the $L$-algorithm writing down the circuit, whose outputs are nearly all directly hardwired to constant.)

> **Comments:**
> **username_0**: It's a bit embarrassing to ask a question with such a trivial well known answer. However, compared to actually spending time trying to separate $L$ from $P$ by simple approaches like looking at the $P$-complete Horn-SAT problem, it makes sense to first ask whether there are known mathematical reasons why we expect that separating $L$ from $NP$ will be difficult.  

---

