Level-p-complexity for Boolean Functions
Typ
Examensarbete för masterexamen
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2022
Författare
Jansson, Julia
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
This thesis concerns characteristics of complexity, specifically level-p-complexity,
for various Boolean functions. Boolean functions are functions f from n bits to one
bit, and they can describe circuits built from logic gates, voting systems as well as
graph properties. An example of a Boolean function is majority, which returns the
value that has majority among the n input bits. Complexity for a Boolean function
f can be seen intuitively as how much information is needed about the input bits
until the result of f is certain. Some well-known notions of complexity for Boolean
functions are deterministic and randomized complexity but in this thesis we focus
on level-p-complexity. Level-p-complexity is defined as the minimum expected cost
over algorithms determining the output, where the input bits are independent and
identically distributed with Bernoulli(p) distribution. The level-p-complexity for a
Boolean function f, is a function of p, so some interesting properties are explored,
such as if it is differentiable, what the maximum is, and if it has more than one
maximum.
First, we calculate the level-p-complexity for the Boolean functions “all” and
“tribes”. Next, we compute the level-p-complexity of majority specifically for three
and five bits and we move on to iterated three bit majority on two levels. Then
we apply Boolean functions to graphs, and we calculate the level-p-complexity for
connectivity of graphs with three or four nodes. All of these examples have in common
that their level-p-complexity is continuous and differentiable and has a unique
maximum, even though a closed form for the maxima of the level-p-complexity of
the tribes function was not found. Finally, we construct a Boolean function whose
level-p-complexity has two maxima. In this case the optimal algorithm depends on
p and the level-p-complexity is piecewise polynomial and thus continuous but not
differentiable in the intersection points.
Future work could include calculating the level-p-complexity for other Boolean
functions or constructing new Boolean functions, and explore properties of their
level-p-complexity.
Beskrivning
Ämne/nyckelord
Boolean functions, level-p-complexity, randomized complexity, deterministic complexity, evasiveness, influence, graph connectivity, iterated majority, Mathematica, Haskell