Average-Case Complexity of Partial Boolean Functions

摘要

The average-case complexity of partial Boolean functions is considered. For almost all functions it is shown that, up to a multiplicative constant, the average-case complexity does not depend on the size of the function's domain but depends only on the number of tuples on which the function is equal to unity.