Boolean Function Complexity - NMAG457

• Anglický název: Boolean Function Complexity
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: Navid Talebanfard
• Třída: M Mgr. MSTR; M Mgr. MSTR > Volitelné

Anotace

čeština

Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (12.05.2022)

The basic approach to the P vs. NP problem is through circuit complexity. Circuits provide a basic model for computing Boolean functions. We will show that several explicit functions cannot be computed by small circuits from various interesting restricted classes.

Literatura

čeština

Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (12.05.2022)

Stasys Jukna, Boolean Function Complexity, Advances and Frontiers, Springer, 2012.

Sylabus

čeština

Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (12.05.2022)

• De Morgan formulas, shrinkage under random restrictions

• Switching lemma, lower bound for the parity function

• Satisfiability coding lemma, depth-3 lower bounds

• Razborov-Smolensky, lower bounds for bounded depth circuits with modular gates