## Level-p-complexity for Boolean Functions

 dc.contributor.author Jansson, Julia dc.contributor.department Chalmers tekniska högskola / Institutionen för matematiska vetenskaper sv dc.contributor.examiner Steif, Jeffrey dc.contributor.supervisor Steif, Jeffrey dc.date.accessioned 2022-05-30T12:01:04Z dc.date.available 2022-05-30T12:01:04Z dc.date.issued 2022 sv dc.date.submitted 2020 dc.description.abstract 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. sv dc.identifier.coursecode MVEX03 sv dc.identifier.uri https://hdl.handle.net/20.500.12380/304584 dc.language.iso eng sv dc.setspec.uppsok PhysicsChemistryMaths dc.subject Boolean functions, level-p-complexity, randomized complexity, deterministic complexity, evasiveness, influence, graph connectivity, iterated majority, Mathematica, Haskell sv dc.title Level-p-complexity for Boolean Functions sv dc.type.degree Examensarbete för masterexamen sv dc.type.uppsok H local.programme Engineering mathematics and computational science (MPENM), MSc
##### Original bundle
Visar 1 - 1 av 1
Hämtar...
Namn:
Master_Thesis_Julia_Jansson_220527.pdf
Storlek:
1.2 MB
Format: