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 |
Ladda ner
Original bundle
1 - 1 av 1
Hämtar...
- Namn:
- Master_Thesis_Julia_Jansson_220527.pdf
- Storlek:
- 1.2 MB
- Format:
- Adobe Portable Document Format
- Beskrivning:
- Level-p-complexity for Boolean Functions
License bundle
1 - 1 av 1
Hämtar...
- Namn:
- license.txt
- Storlek:
- 1.51 KB
- Format:
- Item-specific license agreed upon to submission
- Beskrivning: