On the complexity and depth of circuits that realize partial Boolean functions (Q4367622)

This article deals with circuits that realize partial Boolean functions satisfying the assumption \(FP\neq NC\); here \(FP\) is the class of functions that are sequentially computable in a time polynomial in \(n\) (\(n\) is the number of variables of the function under consideration) and \(NC\) is the class of functions that are computable in a time \((\log_2 n)^{O(1)}\) and with the complexity polynomial in \(n\). The assumption \(FP\neq NC\) means that (i) for any constants \(c_1\), \(c_2\) and \(c_3\) one can find a constant \(n(c_1,c_2,c_3)>0\) such that for any \(n> n(c_1,c_2,c_3)\) there exists a function \(f: \{0,1\}^n\to \{0,1\}\) for which \(L(f)\leq n^{c_1}\) and (ii) if a circuit \(S\) realizes a function \(f\) and \(L(S)\leq (L(f))^{c_2}\), then \(d(S)\geq (\log_2 n)^{c_3}\). The existence of partial Boolean functions \(f\) is established for which the complexity \(L(f)\) and depth \(d(f)\) of circuits cannot be simultaneously close to the minimally possible values, or, in other words, any circuit \(S\) realizing such a function has either the depth or the complexity that significantly exceeds either the depth or the complexity of the function \(f\).