Original title:
Dolní odhady velikosti Booleovských formulí
Translated title:
Lower Bounds on Boolean Formula Size
Authors:
Fojtík, Vít ; Hrubeš, Pavel (advisor) ; Savický, Petr (referee) Document type: Bachelor's theses
Year:
2019
Language:
eng Abstract:
[eng][cze] 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. 1Cı́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
Keywords:
Boolean formula|Formal complexity measure|Lower bounds; Booleovská formule|formální míra složitosti|dolní odhady
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/107745