Clique is not solvable by monotone circuits of polynomial size.
René ThiemannPublished in: Arch. Formal Proofs (2022)
Keyphrases
- polynomial size
- boolean functions
- exponential size
- np complete
- uniform distribution
- dnf formulas
- bounded treewidth
- special case
- conjunctive normal form
- randomly generated
- np hard
- computational complexity
- knowledge compilation
- branch and bound algorithm
- membership queries
- upper bound
- optimal solution
- random instances
- relational databases
- lower bound