Aarhus University Seal / Aarhus Universitets segl

Some results on uniform arithmetic circuit complexity

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
We introduce a natural set of arithmetic expressions and define the complexity class AE to consist of all those arithmetic functions (over the fieldsF 2n) that are described by these expressions. We show that AE coincides with the class of functions that are computable with constant depth and polynomial-size unbounded fan-in arithmetic circuits satisfying a natural uniformity constraint (DLOGTIME-uniformity). A 1-input and 1-output arithmetic function over the fieldsF2n may be identified with ann-input andn-output Boolean function when field elements are represented as bit strings. We prove that if some such representation is X-uniform (where X is P or DLOGTIME), then the arithmetic complexity of a function (measured with X-uniform unbounded fan-in arithmetic circuits) is identical to the Boolean complexity of this function (measured with X-uniform threshold circuits). We show the existence of a P-uniform representation and we give partial results concerning the existence of representations with more restrictive uniformity properties.
Original languageEnglish
JournalTheory of Computing Systems
Volume27
Issue2
Pages (from-to)105-124
Number of pages20
ISSN1432-4350
DOIs
Publication statusPublished - 1994

See relations at Aarhus University Citationformats

ID: 36649481