z-logo
open-access-imgOpen Access
An 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here