Average case complexity for finite Boolean functions.

*(English)*Zbl 1006.94034A straight-line program is a sequence of instructions, each consisting of a unary or binary Boolean function with arguments either input variables or values computed by some previous instructions. A straight-line program with conditional stop may additionally use a two argument stop instruction with the semantics that the computation of the program stops and the second argument is the result of the computation if the first argument is equal to one; otherwise execution of the program is continued with the next instruction. This means that different inputs may lead to computations of different time complexity, and hence it makes sense to talk about the average time complexity to compute a Boolean function. In the present paper it is shown that for almost every Boolean function, the average time complexity is up to a constant factor the same as the usual straight-line program complexity (i.e., Boolean circuit size). On the other hand, a family of functions is constructed that has average time complexity that is (up to a constant factor) less than the usual straight-line program complexity by a factor of \((2^n/n)^{1/2}\).

Reviewer: Heribert Vollmer (Würzburg)

##### MSC:

94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |

68Q25 | Analysis of algorithms and problem complexity |

03D15 | Complexity of computation (including implicit computational complexity) |

##### Keywords:

Boolean function; straight-line program complexity; average case complexity; Boolean circuit size
PDF
BibTeX
XML
Cite

\textit{A. V. Chashkin}, Discrete Appl. Math. 114, No. 1--3, 43--59 (2001; Zbl 1006.94034)

Full Text:
DOI

##### References:

[1] | A.E. Andreev, On circuit complexity of partial Boolean functions, Diskret. Mat. 1(4) (1989) 36-45 (in Russian). · Zbl 0719.94028 |

[2] | O.B. Lupanov, An approach to the synthesis of control systems; the principle of local coding, Problemy Kibernetiki, Moscow, 14 (1965) 31-110 (in Russian). |

[3] | L.A. Sholomov, On the implementation of partial Boolean functions by circuits, Problemy Kibernetiki, Moscow, 21 (1969) 215-226 (in Russian). |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.