Average case complexity for finite Boolean functions

DOI10.1016/S0166-218X(00)00360-7MaRDI QIDQ5954082zbMATH OpenFDO

Authors A. V. Chashkin

Publication date 14 February 2003

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(00)00360-7

zbMATH Keywords

average case complexityBoolean circuit sizeBoolean functionstraight-line program complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Review text

A 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}\).

Recommendations

• scientific article; zbMATH DE number 1037955
• On the average-case complexity of underdetermined functions
• Average-case complexity of elementary Boolean functions
• Bounds for the average-case complexity of monotone Boolean functions
• Average time of computing Boolean operators

Cited in

(13)

• On the average-case complexity of underdetermined functions
• Bounds for the average-case complexity of monotone Boolean functions
• Malign distributions for average case circuit complexity.
• Average complexity of symmetric Boolean functions
• On the average-case complexity of Boolean functions under binomial distribution on their domains
• On the implementation of monotone Boolean functions by memoryless programs
• Average time of computing Boolean operators
• scientific article; zbMATH DE number 1037955 (Why is no real title available?)
• scientific article; zbMATH DE number 1543307 (Why is no real title available?)
• On the realization of linear Boolean operators by straight-line programs with a conditional stop
• Average-case complexity of elementary Boolean functions
• Stochastic Algorithms: Foundations and Applications
• Lower bounds for the complexity of restrictions of Boolean functions

This page was built for publication: Average case complexity for finite Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5954082)