Query Complexity of Search Problems.
Arkadev ChattopadhyayYogesh DahiyaMeena MahajanPublished in: Electron. Colloquium Comput. Complex. (2023)
Keyphrases
- search problems
- query complexity
- orders of magnitude
- search algorithm
- data complexity
- membership queries
- heuristic search
- search strategies
- search space
- dnf formulas
- constraint satisfaction problems
- exact learning
- planning problems
- query answering
- state space
- concept class
- vc dimension
- optimal solution
- pac learning
- constraint programming
- data model
- worst case