Open AccessAn Algebraic Model for Bounding Threshold Circuit Depth
Author(s) -
Joan Boyar,
Gudmund Skovbjerg Frandsen,
Carl Sturtivant
Publication year - 1988
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v17i239.7595
Subject(s) - mathematics , computation , boolean function , algebraic number , constant (computer programming) , boolean circuit , polynomial , function (biology) , integer (computer science) , discrete mathematics , upper and lower bounds , model of computation , electronic circuit , bounding overwatch , measure (data warehouse) , arithmetic , topology (electrical circuits) , algorithm , combinatorics , computer science , mathematical analysis , database , evolutionary biology , artificial intelligence , electrical engineering , biology , programming language , engineering
We define a new structured and general model of computation: circuits using arbitrary fan- in arithmetic gates over the characteristic two finite fields ( F _2n). These circuits have only one input and one output. We show how they correspond naturally to boolean computations with n inputs and n outputs. We show that if circuit sizes are polynomially related then the arithmetic circuit depth and the threshold circuit depth to compute a given function differ by at most a constant factor. We use threshold circuits that allow arbitrary integer weights; however, we show that when compared to the usual threshold model, the depth measure of this generalised model only differs by at most a constant factor (at polynomial size). The fan-in of our arithmetic model is also unbounded in the most generous sense: circuit size is measured as the number of Sum and ½ gates; there is no bound on the number of ''wires'' . We show that these results are provable for any ''reasonable'' correspondance between bit strings of n-bits and elements of F _ 2n. And, we find two distinct characterizations of ''reasonable''. Thus, we have shown that arbitrary fan-in arithmetic computations over F _ 2n constitute a precise abstraction of boolean threshold computations with the pleasant property that various algebraic laws have been recovered.