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.


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.

  • $\begingroup$ Thank you so much. I didn't knew about new version. $\endgroup$ – Mohsen Ghorbani Jul 21 '19 at 5:54

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.