Random Instances of W[2]-Complete Problems: Thresholds, Complexity, and Algorithms.
Yong GaoPublished in: SAT (2008)
Keyphrases
- random instances
- hard problems
- optimization problems
- worst case
- np complete problems
- computational complexity
- phase transition
- np complete
- decision problems
- benchmark problems
- constraint satisfaction problems
- orders of magnitude
- search methods
- search problems
- metaheuristic
- randomly generated
- space complexity
- difficult problems
- sat instances