<p>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.</p>

CC BY-SA 3.0
2012-02-20T20:39:21.910Z
What is "NL^NL(oracle)" ? and how is this different from "NL^NL" ?
Suresh Venkat
CC BY-SA 3.0
2012-02-23T08:11:01.357Z
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$.
Dai Le
CC BY-SA 3.0
2012-02-23T17:45:59.143Z
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.
Kaveh
CC BY-SA 3.0
2012-02-23T18:35:51.603Z
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.
Suresh Venkat
CC BY-SA 3.0
2012-02-23T19:16:04.550Z
I cast a close-vote before the question was changed to its current form.  Not sure what should happen in these situations...
Lev Reyzin
CC BY-SA 3.0
2012-02-23T20:28:01.980Z
The "anonymous editor" was me. I forgot to log in. :-) I don't mind the question being closed. But I tried to be more helpful to the asker with my comment.
Dai Le
CC BY-SA 3.0
2012-02-24T00:04:22.180Z
@Suresh, I agree that the new question is much better and also have mixed feeling about the closing it, but the OP hasn't responded to your and other comments yet. The edit is quite significant in my opinion, from my point of view it was not an evolution (since the OP didn't participate) but a new one. The original one seems to be a homework, I am not sure if changing it to a research-level question is a good idea, subtleties about defining oracle access in logarithmic space is not what the OP was asking, OP was asking for a proof. Maybe we should discuss this and also Lev's point on meta.
Kaveh
CC BY-SA 3.0
2012-02-24T00:08:58.540Z
(I am also fine if you decide to reopen it, considering @Lev's comment that can be a reasonable thing to do. Part of the problem is is that the system doesn't handle close/reopen votes and change of opinion after edits in a nice way. This happens more often on MO often where the number of people who can vote to close is much larger.)
Kaveh
CC BY-SA 3.0
2012-02-24T00:31:24.280Z
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.
Suresh Venkat
<complexity-classes><space-bounded><oracles><nondeterminism><logspace>
Can we show that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? 
albert
# Can we show that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? 

(Asked by: username_0 on 2012-02-20)

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.

**Tags:** complexity-classes, space-bounded, oracles, nondeterminism, logspace

> **Comments:**
> **username_1**: What is "NL^NL(oracle)" ? and how is this different from "NL^NL" ?  
> **username_2**: 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$.  
> **username_3**: 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.  
> **username_1**: 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.  
> **username_4**: I cast a close-vote before the question was changed to its current form.  Not sure what should happen in these situations...  
> **username_2**: The "anonymous editor" was me. I forgot to log in. :-) I don't mind the question being closed. But I tried to be more helpful to the asker with my comment.  
> **username_3**: @Suresh, I agree that the new question is much better and also have mixed feeling about the closing it, but the OP hasn't responded to your and other comments yet. The edit is quite significant in my opinion, from my point of view it was not an evolution (since the OP didn't participate) but a new one. The original one seems to be a homework, I am not sure if changing it to a research-level question is a good idea, subtleties about defining oracle access in logarithmic space is not what the OP was asking, OP was asking for a proof. Maybe we should discuss this and also Lev's point on meta.  
> **username_3**: (I am also fine if you decide to reopen it, considering @Lev's comment that can be a reasonable thing to do. Part of the problem is is that the system doesn't handle close/reopen votes and change of opinion after edits in a nice way. This happens more often on MO often where the number of people who can vote to close is much larger.)  
> **username_1**: 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.  

---

## 0 answers

