5
$\begingroup$

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 for my purpose.

My next idea was to try $A:=TQBF$, where $TQBF$ is the $PSPACE$-complete problem to decide true quantified Boolean formulas. 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 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.

$\endgroup$
  • 1
    $\begingroup$ 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}}$. $\endgroup$ – Emil Jeřábek May 14 '15 at 13:39
  • 1
    $\begingroup$ @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. $\endgroup$ – Thomas Klimpel May 14 '15 at 14:13
  • 4
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek May 14 '15 at 14:26
  • 3
    $\begingroup$ @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. $\endgroup$ – Thomas Klimpel May 14 '15 at 14:44
2
$\begingroup$

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 Emil Jeřábek (see comments) is right: the statement that $TQBF$ is $PSPACE$-complete under logspace many-one reductions is well known.


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 uniform $\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.)

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Klimpel May 21 '15 at 22:38

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.