15

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

domotorp
  • 13,931
  • 37
  • 93
  • 5
    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. – Alessandro Cosentino Oct 04 '13 at 15:08
  • 1
    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. – domotorp Oct 04 '13 at 15:14
  • @domotorp What weight does "no other proof is known" carry? There could be no other proof either because it's difficult to find one or because nobody has felt the need to find one. – David Richerby Oct 04 '13 at 18:52
  • @David: At least it shows that it is not trivial to get rid of group theory. But you are right, maybe no one felt the need to find another... – domotorp Oct 04 '13 at 19:35
  • 1
    Are there any stronger theorems that imply Barrington's theorem? And do they use Barrington's theorem in the proof? – Peter Shor Oct 04 '13 at 19:38
  • @domotorp But it doesn't show that it's not trivial to get rid of the group theory: maybe it's just that nobody has felt sufficiently motivated to try. – David Richerby Oct 04 '13 at 20:23
  • 5
    @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 :) – Alessandro Cosentino Oct 05 '13 at 01:02
  • While the proof is amazing, it does feel like magic. It's worth seeing if that magic is somehow necessary. Is there any reason why the algebra is necessary for this result? – Sasho Nikolov Oct 06 '13 at 05:08
  • 1
    @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? – Peter Shor Nov 10 '13 at 10:49
  • @Peter correct me if I am misunderstanding you: I am thinking of the theorem "polysize formulas have polynomial size constant width branching programs (BPs)". Are you saying that the Barrington's construction works only if a non-solvable group is used (I agree but I am not sure this implies that the algebra is intrinsic to the theorem) or are you saying that there is some sense in which the kind of restricted BPs Barrington considers capture the power of arbitrary bounded-width BPs? – Sasho Nikolov Nov 10 '13 at 23:33
  • 1
    @Sasho: I'm saying your first alternative: Barrington's construction relies on non-solvable groups, so it seems like it's intrinsically algebraic. My comment gives my intuition about this, but it certainly isn't rigorous. – Peter Shor Nov 10 '13 at 23:59

0 Answers0