0
$\begingroup$

I'm reading about autoreducibility, which is the following notion:

A set $L$ is autoreducible if there is a polynomial-time oracle Turing machine $M$ that accepts $L$ using $L$ as an oracle, with the caveat that $M(x)$ may not query whether $x \in L$.

I encountered some results that are confusing me. In Using autoreducibility to separate complexity classes, Buhrman et al. showed that every polynomial-time Turing-complete set for EXPSPACE is autoreducible (Theorem 4.1). In Diagonalization, a survey by Fortnow, there is a theorem stating that if every Turing-complete set for EXPSPACE is autoreducible then $NL \neq NP$ (Theorem 3.1). So using both theorems together, we have $NP \neq NL$! I want to know where is my fault.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The result from Buhrman et al. is about EXP rather than EXPSPACE.

Note that Theorem 3.1 from Fortnow's survey is taken from the very same paper of Buhrman et al.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you so much. I didn't knew about new version. $\endgroup$
    – Mohsen Ghorbani
    Commented Jul 21, 2019 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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