22

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$ ?

Shiva Kintali
  • 10,578
  • 41
  • 74
  • 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. – Derrick Stolee Oct 12 '10 at 21:51
  • @Derrick: could you elaborate in an answer? – András Salamon Oct 13 '10 at 06: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. – Shiva Kintali Oct 13 '10 at 06:59

1 Answers1

11

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.

V Vinay
  • 3,873
  • 1
  • 24
  • 30
  • 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 (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 Oct 15 '10 at 13:29
  • @Vinay, @Ramprasad : Thanks for beautiful insights. – Shiva Kintali Nov 11 '10 at 23:56