Jump to content

Query complexity

From Wikipedia, the free encyclopedia
This is the current revision of this page, as edited by David Eppstein (talk | contribs) at 06:18, 26 March 2025 (+1). The present address (URL) is a permanent link to this version.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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:

See also

[edit]
  • 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