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