# Is every Turing complete set for EXPSPACE autoreducible?

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.

## 1 Answer

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.

• Thank you so much. I didn't knew about new version. Jul 21 '19 at 5:54