Invariance of Complexity Measures for Networks with Unreliable Gates

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1989

Abstract

A new probabilistic failure model for networks of gates is formulated. Although this model has not been used previously, it supports the proofs of both the positive and negative results appearing in the literature. Furthermore, with respect to this new model, the complexity measures of both size and depth are affected by at most constant multiplicative factors when the set of functions that can be computed by gates is changed from one finite and complete basis to another, or when the bound on the failure probability of the gates is changed (within the limits allowed by the basis), or when the bound on the error probability of the network is changed (within the limits allowed by the basis and the failure probability of the gates).

Rights Information

© 1989 Association for Computing Machinery

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Link to Full Text

Share

COinS