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$ ?
$\begingroup$
$\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$– Derrick StoleeOct 12, 2010 at 21:51
-
$\begingroup$ @Derrick: could you elaborate in an answer? $\endgroup$– András SalamonOct 13, 2010 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$– Shiva KintaliOct 13, 2010 at 6:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
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$ Oct 15, 2010 at 13:29
-
$\begingroup$ @Vinay, @Ramprasad : Thanks for beautiful insights. $\endgroup$ Nov 11, 2010 at 23:56