Query complexity
Query complexity in computational complexity describes the number of queries needed to solve a computational problem for an input that can be accessed only through queries. See in particular:
- Aanderaa–Karp–Rosenberg conjecture, on the query complexity of graph problems accessed by querying the existence of edges
- Property testing, the study of query complexity for distinguishing objects having a property from objects far from having it
- Probabilistically checkable proof, a proof that can be verified by making a small number of queries to the bits of the proof
- Quantum complexity theory#Quantum query complexity, the number of queries needed to solve a problem using a quantum algorithm
- Query complexity in the decision tree model, the number of queries needed to solve a computational problem by an algorithm that is restricted to take the form of a decision tree
- Decision tree model#Quantum decision tree, decision tree complexity for a quantum decision tree
- Equitable cake-cutting#Query complexity, the number of times one must query participant preferences in a fair sharing procedure
See also
- Query complexity in database theory, the complexity of evaluating a query on a database when measured as a function of the query size
- Query (complexity), a mapping between logical structures in descriptive complexity