Složitost Booleovských funkcí

• Název práce v češtině: Složitost Booleovských funkcí
• Název v anglickém jazyce: Complexity of Boolean functions
• Akademický rok vypsání: 2008/2009
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: prof. RNDr. Jan Krajíček, DrSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 10.10.2008
• Datum zadání: 10.10.2008
• Datum a čas obhajoby: 29.06.2009 00:00
• Datum odevzdání elektronické podoby: 29.06.2009
• Datum proběhlé obhajoby: 29.06.2009
• Oponenti: prof. Mgr. Michal Koucký, Ph.D.

Zásady pro vypracování

Nastudovat a zpracovat význam spodních odhadů na
složitost Booleovských funkcí, dát příklady takových odhadů,
a popsat koncepční problémy s jejich dokazováním (teorie
Razborova a Rudiche).

Seznam odborné literatury

Ravi Boppana a Mike Sipser, The complexity of finite functions,
in: Handbook of Theoretical Computer Science, Vol.A, ed.J. van Leeuwen, (1990), str.757 - 804.

Alexander A. Razborov, Stephen Rudich, Natural proofs, Proc. of the 26th Annual ACM Symposium
on the Theory of Computing, (1994), str.204-213.

Předběžná náplň práce

Práce se zabývá obvodovou složitostí Booleovských funkcí.

Předběžná náplň práce v anglickém jazyce

The paper is concerned with the circuit complexity of Boolean functions.