On the Pseudo-Deterministic Query Complexity of NP Search Problems.
Shafi GoldwasserRussell ImpagliazzoToniann PitassiRahul SanthanamPublished in: Computational Complexity Conference (2021)
Keyphrases
- search problems
- query complexity
- search algorithm
- orders of magnitude
- data complexity
- heuristic search
- membership queries
- np complete
- search strategies
- exact learning
- search space
- constraint satisfaction problems
- computational complexity
- query evaluation
- planning problems
- vc dimension
- expressive power
- branch and bound
- search strategy
- resource consumption
- reinforcement learning