19
$\begingroup$

I know that you can use other non-solvable groups, but is there a proof that uses a completely different approach?

In case someone would not know the theorem: http://en.wikipedia.org/wiki/NC_(complexity)#Barrington.27s_theorem

$\endgroup$
11
  • 5
    $\begingroup$ The original proof is so beautiful and simple, why seeking an alternative proof? :) More seriously, I wonder if there is any particular motivation behind the question. $\endgroup$ Commented Oct 4, 2013 at 15:08
  • 2
    $\begingroup$ My original motivation is simply that I wanted to tell in class that "no other proof is known"... But besides, I am also interested to know if there is another method, as it might be another good trick to learn. $\endgroup$
    – domotorp
    Commented Oct 4, 2013 at 15:14
  • 1
    $\begingroup$ Are there any stronger theorems that imply Barrington's theorem? And do they use Barrington's theorem in the proof? $\endgroup$ Commented Oct 4, 2013 at 19:38
  • 6
    $\begingroup$ @PeterShor: good point. Ben-Or and Cleve did prove a generalization of Barrington's theorem for algebraic formulas over arbitrary rings. They don't black-box Barrington's theorem, but I wouldn't say that their proof "uses a completely different approach", as the OP requested. AFAIU the magic there happens because of the group SL(3,R) instead of S_5, but it's the same kind of magic :) $\endgroup$ Commented Oct 5, 2013 at 1:02
  • 1
    $\begingroup$ @Sasho: if I remember correctly, Barrington's theorem applies to a group if and only if the group is non-solvable. Doesn't this show that some algebra is necessary? $\endgroup$ Commented Nov 10, 2013 at 10:49

1 Answer 1

8
$\begingroup$

After reading the comments to get clearer on the motivation, I think we can say two things (one from the comments, one perhaps not mentioned yet):

  1. Given the lack of responses, even with attention from many people on this site including many experts, it seems likely that no such alternative proof is currently known.

  2. "Algebra is necessary (given our curren state of complexity understanding)". To clarify/extend some of the comments of Peter Shor and Sasho Nikolov: it's not just that Barrington's particular construction uses non-solvability of the group (which is true), it is that, assuming $\mathsf{NC}^1 \neq \mathsf{ACC}^0$, G-permutation branching programs are $\mathsf{NC}^1$-complete if and only if G is non-solvable. In Barrington's original paper he showed (Theorem 6) that if G is solvable, then G-PBPs can only compute languages in $\mathsf{ACC}^0$.

So, a "truly different proof" seems like it would have to do at least one of two things: either show that $\mathsf{NC}^1 = \mathsf{ACC}^0$, or give a different characterization of non-solvable groups. Now, there are of course many characterizations of solvable groups, so the second possibility seems somewhat plausible (whereas the first seems unlikely to me, though of course we don't even understand the power of MOD$_6$ gates, so who knows how powerful $\mathsf{ACC}^0$ might be...).

And in fact, the $\mathsf{NC}^1=\mathsf{ACC}^0$ alternative above is even more restrictive than as phrased above. I believe it follows from the proof technique of Barrington's Theorem 6 that if $G$ is a group with $\ell$ composition factors, then $G$-PBPs can be simulated by circuits of depth $\ell$, where all the gates at layer $i$ are MOD$_{p_i}$ gates, where $p_i$ is the order of the $i$-th composition factor of $G$. So if one could show that there is some solvable $G$ such that $G$-PBPs capture $\mathsf{NC}^1$, it would put $\mathsf{NC}^1$ into this (seemingly) more restricted subclass of $\mathsf{ACC}^0$.

Barrington, Straubing, and Therien then showed that G-PBPs where G is nilpotent cannot even compute the AND function (that is, for any nilpotent group G, there is a sufficiently large $n$ such that the AND of $n$ bits cannot be computed by any G-PBP, regardless of length). They also showed that when $G$ is solvable, $G$-PBPs can compute the AND function (the upper bound is exponential).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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