21
$\begingroup$

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

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

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.

$\endgroup$
2
  • 4
    $\begingroup$ 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]. $\endgroup$
    – Ramprasad
    Oct 15 '10 at 13:29
  • $\begingroup$ @Vinay, @Ramprasad : Thanks for beautiful insights. $\endgroup$ Nov 11 '10 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.