22
$\begingroup$

Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions functions are permutations (without any restriction on the width). We know from Barrington's famous result and from the fact that arbitrary poly-size branching programs capture exactly logspace that $$\mathsf{NC}^1\subseteq\mathsf{PPBP}\subseteq\mathsf{L}/\mathsf{poly}.$$ In the closing section of his 1989 paper, Barrington briefly considers this question and observes that $\mathsf{PPBP}$ is known to contain $\mathsf{L}$-complete problems under $\mathsf{NC}^1$ reductions. This suggests that the first inclusion above is strict but fails to yield a characterization of $\mathsf{PPBP}$ in terms of a well-known class, because it is not known whether $\mathsf{PPBP}$ is closed under $\mathsf{NC}^1$ reductions (right?).

Has any improvement on understanding the power of permutation branching programs been made since Barrington's work?

Edit: Just for completeness, this is Barrington on what I call here $\mathsf{PPBP}$ (second paragraph of Sect. 8 of his paper "Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in $\mathsf{NC}^1$", Journal of Computer and System Sciences, 38(1):150-164, 1989):

The power of general poly-size permutation BPs (no restriction on width) was mentioned as an open problem in [Barrington's Ph.D. thesis]. Cook and McKenzie [a 1986 tech report] have just shown that [the word problem for permutation groups] is complete for log space under $\mathsf{NC}^1$ reductions [...] A poly-size PBP can be constructed to solve this problem, given an appropriate definition of recognition of a language by a PBP.

The fact that he never explicitly says that poly-size permutation BP are equivalent to poly-size BP led me to assume that having an $\mathsf{L}$-complete problem in $\mathsf{PPBP}$ was not known to be enough to get $\mathsf{PPBP}=\mathsf{L}/\mathsf{poly}$ (e.g., lack of closure under reductions).

Improve this question
$\endgroup$
8
  • $\begingroup$ @Kaveh Sorry, I didn't know that $\mathsf{PBP}$ was the standard notation for poly-size branching programs. I didn't think there even was a standard notation for such a class. I had seen for instance $\mathsf{BP}$ in Vollmer's book (e.g. his Theorem 4.38), but didn't think it was standard either. Anyway, I edited the question, hopefully it is less confusing now. $\endgroup$
    – Damiano Mazza
    Jul 21, 2015 at 19:52
  • 3
    $\begingroup$ Cannot quite see why PPBP could be smaller than L/poly. Take branching program of size S. Make it layered with only one variable tested per layer. Costs only poly(S,n). Then make the fanin of each layer 1. Costs again only poly(S,n). And you have a PPBP. The size of the resulting BP will be much larger, but still polynomial in S. $\endgroup$
    – Stasys
    Jul 21, 2015 at 20:10
  • $\begingroup$ Barrington used the notion PBP for permutation branching programs. On the other hand I don't recall seeing PBP being used for the notion of polynomial size branching programs in the literature! $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jul 22, 2015 at 12:05
  • 2
    $\begingroup$ @Stasys Your observation immediately gives $\mathsf{PPBP}=\mathsf{L}/\mathsf{poly}$ independently of anything mentioned by Barrington (I added a quote to the question), which means that either he was unaware of this observation, or that I am missing what he means by "the power of general poly-size permutation BPs". Anyhow, does your observation appear somewhere in the literature, or is it folklore? $\endgroup$
    – Damiano Mazza
    Jul 22, 2015 at 13:13
  • 3
    $\begingroup$ @Damiano: This was just a spontaneous, few minutes intuition: we only need to keep width within poly(n,S), a huge freedom. So, adding enough dummy nodes "should" suffice, but I haven't checked the details. And no, I don't think this was considered somewhere in the literature. Just because the whole beauty of Barrington's result lies in width being only 5(!), not poly(n). $\endgroup$
    – Stasys
    Jul 22, 2015 at 16:52

0

Reset to default

Your Answer

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