4
$\begingroup$

$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$?

$\endgroup$
4
  • 4
    $\begingroup$ $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. $\endgroup$ Jun 4 at 13:38
  • 4
    $\begingroup$ 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. $\endgroup$ Jun 4 at 14:12
  • $\begingroup$ How do composition factors relate to the family of programs and their circuits? $\endgroup$
    – Mr.
    Jun 4 at 21:51
  • 1
    $\begingroup$ I recommend to look in the following book. Howard Straubing. Finite automata, formal logic, and circuit complexity. $\endgroup$ Jun 12 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.