Název: Dolní odhady velikosti Booleovských formulí
Překlad názvu: Lower Bounds on Boolean Formula Size
Autoři: Fojtík, Vít ; Hrubeš, Pavel (vedoucí práce) ; Savický, Petr (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2019
Jazyk: eng
Abstrakt: [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. 1 Cı́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
Klíčová slova: Booleovská formule|formální míra složitosti|dolní odhady; Boolean formula|Formal complexity measure|Lower bounds

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/107745

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-398240


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce