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

In descriptive complexity, a query is a mapping from structures of one signature to structures of another vocabulary. Neil Immerman, in his book Descriptive Complexity, "use[s] the concept of query as the fundamental paradigm of computation" (p. 17). Given signatures \sigma and \tau , we define the set of structures on each language, \mbox{STRUC}[\sigma] and \mbox{STRUC}[\tau] . A query is then any mapping I : \mbox{STRUC}[\sigma] \to \mbox{STRUC}[\tau] Computational complexity theory can then be phrased in terms of the power of the mathematical logic necessary to express a given query. ==Order-independent queries== A query is order-independent if the ordering of objects in the structure does not affect the results of the query. In databases, these queries correspond to generic queries (Immerman 1999, p. 18). A query is order-independent iff I(\mathfrak{A}) \equiv I(\mathfrak{B}) for any isomorphic structures \mathfrak{A} and \mathfrak{B} . ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1282406700 under CC BY-SA 4.0; modifications have been made.