<p>Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of <em>permutation</em> branching programs, which are layered branching programs (i.e., the ones defined <a href="https://en.wikipedia.org/wiki/NC_%28complexity%29#Barrington.27s_theorem" rel="noreferrer">here</a>) 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 <a href="http://people.cs.umass.edu/~barring/publications/bwbp.pdf" rel="noreferrer">his 1989 paper</a>, 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?).</p>

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

<hr>

<p><strong>Edit:</strong> 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$", <em>Journal of Computer and System Sciences</em>, 38(1):150-164, 1989):</p>

<p><code>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.</code></p>

<p>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).</p>

CC BY-SA 3.0
2015-07-21T19:52:50.430Z
@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.
Damiano Mazza
CC BY-SA 3.0
2015-07-21T20:10:42.667Z
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.
Stasys
CC BY-SA 3.0
2015-07-22T12:05:38.023Z
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!
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2015-07-22T12:09:35.620Z
Stasys: How do you make the fanin 1 in each layer?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2015-07-22T12:27:22.570Z
@Stasys Thank you! I see what you mean and it actually seems to work (I'm sorry, I am a "theory B" guy and am a bit slow with these things).  If I uderstand correctly, your second transformation (to obtain fan-in 1) "combs" through the layered BP adding states whenever the fan-in exceeds 1.  For instance, the function $\{1\mapsto 1,2\mapsto 1\}$ becomes $\{1\mapsto 1,2\mapsto 1'\}$ (width increases from 2 to 3). In this way, we obtain a BP with as many layers as the original one, but whose width increases in each layer, and the transitions functions are obviously injective.  (continued below)
Damiano Mazza
CC BY-SA 3.0
2015-07-22T12:35:45.727Z
From the above, it is not too hard to obtain a permutation BP: we just need to add extra states to each layer, so that it becomes as wide as the last, and map these extra states to the states of the following layer which are not in the range of the (injective) transition function.  I agree that this transformation has a polynomial cost.  My only doubt concerns the fact that each layer has two transition functions, which must be "injectivized" consistently with each other, in order not to loose the behavior of the original BP. But I believe you if you think it works.
Damiano Mazza
CC BY-SA 3.0
2015-07-22T13:13:15.683Z
@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?
Damiano Mazza
CC BY-SA 3.0
2015-07-22T16:52:12.450Z
@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).
Stasys
<cc.complexity-theory><complexity-classes><circuit-complexity><logspace><structural-complexity>
What is the power of general poly-size permutation branching programs?
Damiano Mazza
# What is the power of general poly-size permutation branching programs?

(Asked by: username_0 on 2015-07-20)

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](https://en.wikipedia.org/wiki/NC_%28complexity%29#Barrington.27s_theorem)) 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](http://people.cs.umass.edu/~barring/publications/bwbp.pdf), 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).

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, logspace, structural-complexity

> **Comments:**
> **username_0**: @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.  
> **username_1**: 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.  
> **username_2**: 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!  
> **username_2**: username_1: How do you make the fanin 1 in each layer?  
> **username_0**: @username_1 Thank you! I see what you mean and it actually seems to work (I'm sorry, I am a "theory B" guy and am a bit slow with these things).  If I uderstand correctly, your second transformation (to obtain fan-in 1) "combs" through the layered BP adding states whenever the fan-in exceeds 1.  For instance, the function $\{1\mapsto 1,2\mapsto 1\}$ becomes $\{1\mapsto 1,2\mapsto 1'\}$ (width increases from 2 to 3). In this way, we obtain a BP with as many layers as the original one, but whose width increases in each layer, and the transitions functions are obviously injective.  (continued below)  
> **username_0**: From the above, it is not too hard to obtain a permutation BP: we just need to add extra states to each layer, so that it becomes as wide as the last, and map these extra states to the states of the following layer which are not in the range of the (injective) transition function.  I agree that this transformation has a polynomial cost.  My only doubt concerns the fact that each layer has two transition functions, which must be "injectivized" consistently with each other, in order not to loose the behavior of the original BP. But I believe you if you think it works.  
> **username_0**: @username_1 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?  
> **username_1**: @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).  

---

## 0 answers

