Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture.
Anil KamathRajeev MotwaniKrishna V. PalemPaul G. SpirakisPublished in: Random Struct. Algorithms (1995)
Keyphrases
- upper bound
- satisfiability problem
- lower bound
- computational complexity
- upper and lower bounds
- lower and upper bounds
- terminological reasoning
- threshold selection
- worst case
- propositional logic
- machine learning
- heavy tailed
- stochastic local search
- error bounds
- neural network
- vc dimension
- computational properties
- decision procedures
- symmetry breaking
- np complete
- reasoning problems
- search algorithm
- adaptive threshold