The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems.
Alan M. FriezeMichael MolloyPublished in: RANDOM-APPROX (2003)
Keyphrases
- randomly generated
- np complete
- phase transition
- sat problem
- sat instances
- satisfiability problem
- branch and bound algorithm
- stochastic local search
- boolean functions
- constraint satisfaction
- branch and bound
- propositional logic
- integer programming formulation
- constraint problems
- constraint satisfaction problems
- np hard
- neural network
- cnf formula
- boolean formula
- simplex algorithm
- np complete problems
- lower bound