Random Strings Make Hard Instances.
Harry BuhrmanPekka OrponenPublished in: J. Comput. Syst. Sci. (1996)
Keyphrases
- random instances
- randomly generated
- phase transition
- sat instances
- lower bound
- constraint satisfaction problems
- random sat
- closest string
- edit distance
- hard problems
- truth assignment
- randomly chosen
- instance space
- np complete problems
- sat solvers
- decision trees
- np complete
- random sat instances
- training instances
- sat problem
- constraint satisfaction
- case study