The relative complexity of NP search problems.
Paul BeameStephen A. CookJeff EdmondsRussell ImpagliazzoToniann PitassiPublished in: STOC (1995)
Keyphrases
- search problems
- search algorithm
- orders of magnitude
- heuristic search
- computational complexity
- state space search
- search strategies
- efficient search
- search space
- solving hard
- beam search
- heuristic search algorithms
- parallel processors
- np complete
- iterative deepening
- constraint satisfaction problems
- general purpose
- dynamic programming
- parallel version