We know by Immerman–Szelepcsényi theorem that $\mathsf{NL}=\mathsf{coNL}$? Does it follow from this theorem that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? Here, $\mathsf{NL}^\mathsf{NL}$ denotes the class of problems which can be solved by an $\mathsf{NL}$ machine with access to an $\mathsf{NL}$ oracle.

  • 1
    $\begingroup$ What is "NL^NL(oracle)" ? and how is this different from "NL^NL" ? $\endgroup$ – Suresh Venkat Feb 20 '12 at 20:39
  • 10
    $\begingroup$ Actually, this question is not as trivial as it looks. The main problem is with the definition of oracle for NL machines. Without careful restriction, e.g. the one by Ruzzo, Simon and Tompa, the oracle tape can be used as addition storage, and thus we can even show that $SAT \in NL^{L}$ as follows. Copy the input formula $\phi$ to the oracle tape, and then nondeterministically write an assignment $\sigma$ on the oracle tape. Next, we ask the oracle for L if $\sigma$ satisfies $\phi$. $\endgroup$ – Dai Le Feb 23 '12 at 8:11
  • 2
    $\begingroup$ The question is now significantly different from what was asked by the original OP: "How can we show that NL^NL(oracle) using this claim NL=coNL". There is no background or motivation provided and to me it seems like an undergraduate homework-level question in complexity. Although what Dai wrote is correct and I agree with it, and the current version written by an anonymous editor is much better, the original question was not. It was off-topic IMO and therefore I am casting the last vote to close it. $\endgroup$ – Kaveh Feb 23 '12 at 17:45
  • $\begingroup$ I have mixed feelings about the closure of this question. Maybe the original question wasn't well formed, but it has evolved into an interesting question. It seems a little quick to close it without letting the new question sit for a while. $\endgroup$ – Suresh Venkat Feb 23 '12 at 18:35
  • 1
    $\begingroup$ It is possible to add reopen votes. If people feel that it's worthy of reopening, they can vote, and I'd be willing to tip things over the edge. But I don't want to force a reopen. $\endgroup$ – Suresh Venkat Feb 24 '12 at 0:31