<p>Since we don't seem to have any answers, can I make a comment?</p>

<p>Suppose we are given $n$ bits, $X=x_1,\cdots,x_n$ and we have to complement each bit to get $\neg x_1,\cdots, \neg x_n.$ The only constraint is that the circuit that does so should be monotone. We obviously need some additional information to do this and here is one such. </p>

<p>Suppose $k$ is the number of ones in the input and somehow we have this as advice. Then it is easy to see that $\neg x_i = Th^{n-1}_{k}(X-x_i)$ (i.e., on all inputs except $x_i$). Of course, the construction is monotone.</p>

<p>With this construction, the motivation for inductive counting is clear (at least to me). It is worth asking what <em>other</em> advice would work? I don't know of any other. But this may hold the key to your question.</p>

CC BY-SA 2.5
2010-11-11T23:56:17.000Z
@Vinay, @Ramprasad : Thanks for beautiful insights.
Shiva Kintali
CC BY-SA 2.5
2010-10-15T13:29:02.663Z
Just adding to this thread. The number of ones in the input can be "guessed" by a binary search and it can be shown therefore that in order to negate n bits, we only need $O(\log n)$ negations. This is a well-known [theorem of Markov](http://portal.acm.org/citation.cfm?id=320945") (for those who haven't seen it, it is a very nice exercise). In fact, for general functions $f$, one can limit the number of negations required to compute $f$ by the log of the number of times $f$ "changes sign" as we go from the all zeroes input to the all ones input [by Fischer, I think].
Ramprasad
CC BY-SA 2.5
2010-10-15T03:03:27.283Z
2010-10-15T03:03:27.283Z
V Vinay
<p><a href="http://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem">Immerman and Szelepcsenyi</a> independently proved that $NL=coNL$. Using their technique of inductive counting, <a href="http://portal.acm.org/citation.cfm?id=68485">Borodin et al</a> proved that $SAC^i$ is closed under complementation, for $i > 0$. Prior to Reingold's theorem ($SL=L$), <a href="http://portal.acm.org/citation.cfm?id=225101">Nisan and Ta-Shma</a> proved $SL=coSL$, using logspace uniform projection reductions. A 1996 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2351">paper</a> of Alvarez and Greenlaw states "A proof of $NL=coNL$ using techniques similar to Nisan and Ta-Shma's has not been achieved although such a proof would be very interesting". I am wondering if such a proof is found in the last 14 years. Are there any other alternate proofs of $NL=coNL$ ?</p>

CC BY-SA 2.5
2010-10-12T21:51:33.403Z
A very similar style of proof is given by Reinhardt and Allender, "Making nondeterminism unambiguous" to prove that st-reachability graphs with a unique min-length path between s and t can be decided in UL \cap coUL.
Derrick Stolee
CC BY-SA 2.5
2010-10-13T06:46:20.530Z
@Derrick: could you elaborate in an answer?
András Salamon
CC BY-SA 2.5
2010-10-13T06:59:57.303Z
@András : Reinhardt and Allender's paper uses inductive counting and isolation lemma to show that NL/poly = UL/poly i.e., in the context of nonuniform complexity, nondeterministic logspace bounded computation can be made unambiguous. This is a nice related result but doesn't deserve to be added as an answer.
Shiva Kintali
<cc.complexity-theory><space-bounded>
Alternate proofs of Immerman-Szelepcsenyi theorem
Shiva Kintali
# Alternate proofs of Immerman-Szelepcsenyi theorem

(Asked by: username_0 on 2010-10-12)

[Immerman and Szelepcsenyi](http://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem) independently proved that $NL=coNL$. Using their technique of inductive counting, [Borodin et al](http://portal.acm.org/citation.cfm?id=68485) proved that $SAC^i$ is closed under complementation, for $i > 0$. Prior to Reingold's theorem ($SL=L$), [Nisan and Ta-Shma](http://portal.acm.org/citation.cfm?id=225101) proved $SL=coSL$, using logspace uniform projection reductions. A 1996 [paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2351) of Alvarez and Greenlaw states "A proof of $NL=coNL$ using techniques similar to Nisan and Ta-Shma's has not been achieved although such a proof would be very interesting". I am wondering if such a proof is found in the last 14 years. Are there any other alternate proofs of $NL=coNL$ ?

**Tags:** cc.complexity-theory, space-bounded

> **Comments:**
> **username_1**: A very similar style of proof is given by Reinhardt and Allender, "Making nondeterminism unambiguous" to prove that st-reachability graphs with a unique min-length path between s and t can be decided in UL \cap coUL.  
> **username_2**: @Derrick: could you elaborate in an answer?  
> **username_0**: @András : Reinhardt and Allender's paper uses inductive counting and isolation lemma to show that NL/poly = UL/poly i.e., in the context of nonuniform complexity, nondeterministic logspace bounded computation can be made unambiguous. This is a nice related result but doesn't deserve to be added as an answer.  

---

## 1 answers

### Answer by username_3 on 2010-10-15. Score: 11 | Accepted answer

Since we don't seem to have any answers, can I make a comment?

Suppose we are given $n$ bits, $X=x\_1,\cdots,x\_n$ and we have to complement each bit to get $\neg x\_1,\cdots, \neg x\_n.$ The only constraint is that the circuit that does so should be monotone. We obviously need some additional information to do this and here is one such.

Suppose $k$ is the number of ones in the input and somehow we have this as advice. Then it is easy to see that $\neg x\_i = Th^{n-1}\_{k}(X-x\_i)$ (i.e., on all inputs except $x\_i$). Of course, the construction is monotone.

With this construction, the motivation for inductive counting is clear (at least to me). It is worth asking what *other* advice would work? I don't know of any other. But this may hold the key to your question.

> **Comments:**
> **username_4**: Just adding to this thread. The number of ones in the input can be "guessed" by a binary search and it can be shown therefore that in order to negate n bits, we only need $O(\log n)$ negations. This is a well-known [theorem of Markov](http://portal.acm.org/citation.cfm?id=320945") (for those who haven't seen it, it is a very nice exercise). In fact, for general functions $f$, one can limit the number of negations required to compute $f$ by the log of the number of times $f$ "changes sign" as we go from the all zeroes input to the all ones input [by Fischer, I think].  
> **username_0**: @Vinay, @username_4 : Thanks for beautiful insights.  

---

