No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random
Russell ImpagliazzoLeonid A. LevinPublished in: FOCS (1990)
Keyphrases
- random instances
- randomly generated
- phase transition
- np complete
- uniformly distributed
- computational complexity
- automatically generate
- automatically generating
- lower bound
- artificial intelligence
- hard problems
- np hard
- constraint satisfaction problems
- data sets
- np complete problems
- learning algorithm
- double exponential
- integer programming