Favorite Theorem 3
Favorite Theorem 3
- Razborov:
- The general clique function does not have polynomial-size monotone circuits.
- Proof uses approximation method:
- Approximate each and/or
- Final circuit must deviate from clique on many graphs
- Thus must have had many gates