Boolean circuits versus arithmetic circuits

We compare the two computational models of Boolean circuits and arithmetic circuits in cases where they both apply, namely the computation of polynomials over the rational numbers or over finite fields. Over Q and finite fields, Boolean circuits can simulate arithmetic circuits efficiently with respect to size. Over finite fields of small characteristic, the two models are equally powerful when size is considered, but Boolean circuits are exponentially more powerful than arithmetic circuits with respect to depth. Most of the technical results given in this synopis are taken from the literature.

Authors

• Joachim von zur Gathen
• Gadiel Seroussi

Keywords

No keywords are indexed for this paper.