Lower Bounds on Boolean Formula Size
Dolní odhady velikosti Booleovských formulí
bakalářská práce (OBHÁJENO)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/107745Identifikátory
SIS: 205426
Kolekce
- Kvalifikační práce [23420]
Autor
Vedoucí práce
Oponent práce
Savický, Petr
Fakulta / součást
Filozofická fakulta
Obor
Logika
Katedra / ústav / klinika
Katedra logiky
Datum obhajoby
19. 6. 2019
Nakladatel
Univerzita Karlova, Filozofická fakultaJazyk
Angličtina
Známka
Výborně
Klíčová slova (česky)
Booleovská formule|formální míra složitosti|dolní odhadyKlíčová slova (anglicky)
Boolean formula|Formal complexity measure|Lower boundsCı́lem této práce je studovat metody konstrukce dolnı́ch odhadů velikosti Booleovských formulı́. Soustředı́me se zde předevšı́m na formálnı́ mı́ry složitosti, přičemž zobecnı́me známou Krapchenkovu mı́ru na třı́du grafových měr, které následně studujeme. Zabýváme se také dalšı́m z hlavnı́ch přı́stupů, využı́vajı́cı́ náhodné restrikce Booleovských funkcı́. Na závěr zmı́nı́me program pro nalezenı́ super-polynomiálnı́ch odhadů založený na KRW doměnce. 1
The aim of this thesis is to study methods of constructing lower bounds on Boolean formula size. We focus mainly on formal complexity measures, gener- alizing the well-known Krapchenko measure to a class of graph measures, which we thereafter study. We also review one of the other main approaches, using ran- dom restrictions of Boolean functions. This approach has yielded the currently largest lower bounds. Finally, we mention a program for finding super-polynomial bounds based on the KRW conjecture. 1