Sylabus
- 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
Anotace
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.