ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION.

Published

Journal Article

The author investigates the computational power of threshold circuits. He discovers a relationship with another class of unbounded fan-in circuits which he denotes finite field Z//P//(//n//) circuits, where each node computes either multiple sums or products of integers modulo a prime P(n). In particular, he proves that all functions computed by threshold circuits of size S(n) greater than equivalent to n and depth D(n) can also be computed by Z//P//(//n//) circuits of size O(S(n) plus nP(n)) and depth O(D(n)). Furthermore, he proves that all functions computed by Z//P//(//n//) circuits of size S(n) and depth D(n) can be computed by threshold circuits of size (S(n)logP(n))**O**(**1**) and depth O(D(n)).

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • January 1, 1987

Start / End Page

  • 118 - 123

Citation Source

  • Scopus