## ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION.

Publication
, Journal Article

Reif, JH

January 1, 1987

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 Scholars

## Publication Date

January 1, 1987

## Start / End Page

118 / 123

### Citation

APA

Chicago

ICMJE

MLA

NLM

Reif, J. H. (1987). ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION., 118–123.

Reif, J. H. “ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION.,” January 1, 1987, 118–23.

Reif JH. ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION. 1987 Jan 1;118–23.

Reif, J. H.

*ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION.*Jan. 1987, pp. 118–23.Reif JH. ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION. 1987 Jan 1;118–123.

## Publication Date

January 1, 1987

## Start / End Page

118 / 123