Complexity of sequential computations of partial Boolean functions by circuits
L. A. Sholomov · Journal of Applied and Industrial Mathematics · 2008
A pair (f, g) of partial Boolean functions is characterized by a tuple of parameters l αβ that is the number of tuples $$ \tilde x $$ such that (f( $$ \tilde x $$ ), g( $$ \tilde x $$ )) = (α, β), where α and β take the values 0, 1, and an undefined value. The sequential computation of (f, g) is considered when a circuit S f for f is constructed first, and, next, it is completed by the construction up to a circuit S f,g . It is shown that if the domain D(f) includes D(g) then it is possible to compute sequentially f and g in such a way that S f and S f,g are asymptotically minimal simultaneously (i.e., they satisfy the asymptotically best bounds on the complexity for corresponding classes); and, in general, these functions cannot be sequentially computed in the order g, f so that S g and S f,g are asymptotically minimal. An attainable lower bound is obtained on the size of the circuit S f,g for the sequential computation. The information properties of partially defined data play an essential role whose study in the previous papers of the author is continued here.