<p><span class="math-container">$L$</span> can be computed by a family of programs over <span class="math-container">$S_3$</span>
of polynomial length if and only if <span class="math-container">$L$</span> can be computed by a family of <span class="math-container">$MOD3 ◦ MOD2$</span> circuits of
polynomial size.</p>
<p><span class="math-container">$L$</span> can be computed by a family of programs over <span class="math-container">$S_5$</span>
of polynomial length if and only if <span class="math-container">$L$</span> can be computed by a family of <span class="math-container">$NC^1$</span> circuits of
polynomial size.</p>
<p>How about if <span class="math-container">$L$</span> can be computed by a family of programs over <span class="math-container">$S_4$</span>?</p>

CC BY-SA 4.0
2021-06-04T13:38:03.567Z
$S_4$ is solvable with composition factors $C_2$ (3 times) and $C_3$, thus you get again some low-depth combination of MOD2 and MOD3 gates.
Emil Jeřábek
CC BY-SA 4.0
2021-06-04T14:12:54.750Z
Yeah, I seem to recall that b/c the (unique?) composition series is $1 \unlhd C_2 \times C_2 \unlhd A_4 \unlhd S_4$, that more specifically you get (perhaps a subfamily of) $MOD_2 \circ MOD_3 \circ MOD_2$ circuits.
Joshua Grochow
CC BY-SA 4.0
2021-06-04T21:51:18.817Z
How do composition factors relate to the family of programs and their circuits?
Turbo
CC BY-SA 4.0
2021-06-12T12:25:36.087Z
I recommend to look in the following book. Howard Straubing. Finite automata, formal logic, and circuit complexity.
Kristoffer Arnsfelt Hansen
<cc.complexity-theory><complexity-classes><circuit-complexity><big-picture><permutations>
What does width $4$ permutation branching program correspond to?
Turbo
# What does width $4$ permutation branching program correspond to?

(Asked by: username_0 on 2021-06-03)

$L$ can be computed by a family of programs over $S\_3$
of polynomial length if and only if $L$ can be computed by a family of $MOD3 ◦ MOD2$ circuits of
polynomial size.

$L$ can be computed by a family of programs over $S\_5$
of polynomial length if and only if $L$ can be computed by a family of $NC^1$ circuits of
polynomial size.

How about if $L$ can be computed by a family of programs over $S\_4$?

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, big-picture, permutations

> **Comments:**
> **username_1**: $S_4$ is solvable with composition factors $C_2$ (3 times) and $C_3$, thus you get again some low-depth combination of MOD2 and MOD3 gates.  
> **username_2**: Yeah, I seem to recall that b/c the (unique?) composition series is $1 \unlhd C_2 \times C_2 \unlhd A_4 \unlhd S_4$, that more specifically you get (perhaps a subfamily of) $MOD_2 \circ MOD_3 \circ MOD_2$ circuits.  
> **username_0**: How do composition factors relate to the family of programs and their circuits?  
> **username_3**: I recommend to look in the following book. Howard Straubing. Finite automata, formal logic, and circuit complexity.  

---

## 0 answers

