|
On the complexity and depth of circuits realizing partial Boolean functions
A. V. Chashkin
Abstract:
The complexity and depth of circuits that realize partial Boolean functions are studied under the assumption that $FP\neq NC$. It is established that there exist partial Boolean functions for which the complexity and depth of circuits cannot be simultaneously close to the minimally possible values, i.e., any circuit realizing such a function has either a depth or a complexity that considerably exceeds either the depth or the complexity of the function which it realizes.
Received: 30.09.1994
Citation:
A. V. Chashkin, “On the complexity and depth of circuits realizing partial Boolean functions”, Diskr. Mat., 9:2 (1997), 53–58; Discrete Math. Appl., 7:2 (1997), 113–118
Linking options:
https://www.mathnet.ru/eng/dm463https://doi.org/10.4213/dm463 https://www.mathnet.ru/eng/dm/v9/i2/p53
|
Statistics & downloads: |
Abstract page: | 572 | Full-text PDF : | 416 | First page: | 1 |
|