Portal de Periódicos da CAPES

Boolean circuits versus arithmetic circuits

1991; Elsevier BV; Volume: 91; Issue: 1 Linguagem: Inglês

10.1016/0890-5401(91)90078-g

1090-2651

Joachim von zur Gathen, G. Seroussi,

Machine Learning and Algorithms

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.