RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1997 Volume 9, Issue 2, Pages 53–58 (Mi dm463)

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.

UDC: 519.7

Received: 30.09.1994

DOI: 10.4213/dm463


 English version:
Discrete Mathematics and Applications, 1997, 7:2, 113–118

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024