velikost textu

Lower Bounds on Boolean Formula Size

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Lower Bounds on Boolean Formula Size
Název v češtině:
Dolní odhady velikosti Booleovských formulí
Typ:
Bakalářská práce
Autor:
Bc. Vít Fojtík
Vedoucí:
Mgr. Pavel Hrubeš, Ph.D.
Oponent:
RNDr. Petr Savický, CSc.
Id práce:
205426
Fakulta:
Filozofická fakulta (FF)
Pracoviště:
Katedra logiky (21-KLOG)
Program studia:
Logika (B6142)
Obor studia:
Logika (LG)
Přidělovaný titul:
Bc.
Datum obhajoby:
19. 6. 2019
Výsledek obhajoby:
Výborně
Jazyk práce:
Angličtina
Klíčová slova:
Booleovská formule|formální míra složitosti|dolní odhady
Klíčová slova v angličtině:
Boolean formula|Formal complexity measure|Lower bounds
Abstrakt:
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
Abstract v angličtině:
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
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Vít Fojtík 506 kB
Stáhnout Abstrakt v českém jazyce Bc. Vít Fojtík 45 kB
Stáhnout Abstrakt anglicky Bc. Vít Fojtík 45 kB
Stáhnout Posudek vedoucího Mgr. Pavel Hrubeš, Ph.D. 28 kB
Stáhnout Posudek oponenta RNDr. Petr Savický, CSc. 73 kB
Stáhnout Záznam o průběhu obhajoby doc. RNDr. Vítězslav Švejdar, CSc. 152 kB