Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique.
David GamarnikElchanan MosselIlias ZadikPublished in: CoRR (2023)
Keyphrases
- lower bound
- random sat
- max sat
- branch and bound algorithm
- upper bound
- phase transition
- boolean satisfiability
- sat problem
- satisfiability problem
- branch and bound
- random constraint satisfaction problems
- random sat instances
- objective function
- random instances
- np hard
- stochastic local search
- sat solvers
- vc dimension
- randomly generated
- search tree
- knowledge base