Exploring level-p-complexity for subclasses of Boolean functions

Abstract

Boolean functions, which map n-bit inputs to a single output bit, can be used to describe digital systems, from logic gates to voting mechanisms. A key challenge lies in measuring the cost of evaluating such functions, specifically the number of input bits required to determine the output with certainty. Among various complexity measures, level-p-complexity, 𝐷𝑝(𝑓), evaluates the expected cost when input bits follow a Bernoulli(p) distribution. This paper aims to optimize an algorithm for computing level-p-complexities developed by Jansson and Jansson [1], as well as develop tools for further exploring level-p-complexity.

Key contributions include optimized algorithms for computing level-p-complexity through techniques such as hash-consing and minimization, which enhance memoization efficiency. Specialized representations for subclasses of Boolean functions, such as symmetric and threshold functions, enable faster computations for specific cases.

Furthermore, this work introduces tools to analyze piecewise polynomial representations of level-p-complexity, focusing on identifying critical points using algebraic numbers for exact calculations. A large number of properties have been implemented using QuickCheck to generate diverse test cases and increase confidence in the correctness of the algorithms.