Lower Bounds on Boolean Formula Size

• Název práce v češtině: Dolní odhady velikosti Booleovských formulí
• Název v anglickém jazyce: Lower Bounds on Boolean Formula Size
• Klíčová slova: Booleovská formule|formální míra složitosti|dolní odhady
• Klíčová slova anglicky: Boolean formula|Formal complexity measure|Lower bounds
• Akademický rok vypsání: 2018/2019
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra logiky (21-KLOG)
• Vedoucí / školitel: Mgr. Pavel Hrubeš, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 25.09.2018
• Datum zadání: 01.10.2018
• Schválení administrátorem: zatím neschvalováno
• Datum potvrzení stud. oddělením: 17.01.2019
• Datum a čas obhajoby: 19.06.2019 10:00
• Datum odevzdání elektronické podoby: 17.05.2019
• Datum proběhlé obhajoby: 19.06.2019
• Odevzdaná/finalizovaná: odevzdaná studentem a finalizovaná
• Oponenti: RNDr. Petr Savický, CSc.

Zásady pro vypracování

Práce se bude zabývat Booleovskými formulemi a jejich velikostí.
Student se seznámí se základními metodami konstrukce dolních odhadů (Nechiporuk, Krapchenko, ...) a uvede stručný přehled. V další části prozkoumá pojmy formální míry složitosti, kombinatorických obdélníků a jejich měr a porovná vztahy s předchozím. Práce by také měla obsahovat vlastní příklady aplikace metod na konkrétní Booleovské funkce.

Seznam odborné literatury

I. Wegener, The Complexity of Boolean Functions, 1987.
P. Hrubeš, S. Jukna, A. Kulikov, P. Pudlák, On Convex Complexity Measures, 2010.
M.Karchmer, E. Kushilevitz, N. Nisan, Fractional covers and communication complexity, 1995.
M. V. Khrapchenko, A method for obtaining lower bounds for the complexity of pi-schemes, 1972.