Random Strings Make Hard Instances.
Harry BuhrmanPekka OrponenPublished in: Computational Complexity Conference (1994)
Keyphrases
- random instances
- randomly generated
- phase transition
- constraint satisfaction problems
- hard problems
- lower bound
- random sat
- closest string
- np complete problems
- truth assignment
- finite automata
- np complete
- sat instances
- uniformly distributed
- randomly chosen
- instance space
- branch and bound algorithm
- scheduling problem
- data sets