# Alternate proofs of Immerman-Szelepcsenyi theorem

Immerman and Szelepcsenyi independently proved that $NL=coNL$. Using their technique of inductive counting, Borodin et al proved that $SAC^i$ is closed under complementation, for $i > 0$. Prior to Reingold's theorem ($SL=L$), Nisan and Ta-Shma proved $SL=coSL$, using logspace uniform projection reductions. A 1996 paper 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$ ?

• 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. Oct 12 '10 at 21:51
• @Derrick: could you elaborate in an answer? Oct 13 '10 at 6:46
• @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. Oct 13 '10 at 6:59

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.
• 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 (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]. Oct 15 '10 at 13:29