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.