http://debianws.lexgopc.com/wiki143/index.php?action=history&feed=atom&title=Query_complexity 2026-10-28T08:32:40Z Revision history for this page on the wiki MediaWiki 1.43.1 http://debianws.lexgopc.com/wiki143/index.php?title=Query_complexity&diff=8832114&oldid=prev 2025-03-26T06:18:34Z

<p>+1</p> <p><b>New page</b></p><div>&#039;&#039;&#039;Query complexity&#039;&#039;&#039; 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:<br /> * [[Aanderaa–Karp–Rosenberg conjecture]], on the query complexity of graph problems accessed by querying the existence of edges<br /> * [[Property testing]], the study of query complexity for distinguishing objects having a property from objects far from having it<br /> * [[Probabilistically checkable proof]], a proof that can be verified by making a small number of queries to the bits of the proof<br /> * [[Quantum complexity theory#Quantum query complexity]], the number of queries needed to solve a problem using a quantum algorithm<br /> * 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<br /> * [[Decision tree model#Quantum decision tree]], decision tree complexity for a quantum decision tree<br /> * [[Equitable cake-cutting#Query complexity]], the number of times one must query participant preferences in a fair sharing procedure<br /> <br /> ==See also==<br /> * [[Query_evaluation#Formal_definition|Query complexity]] in database theory, the complexity of evaluating a query on a database when measured as a function of the query size<br /> *[[Query (complexity)]], a mapping between logical structures in descriptive complexity<br /> <br /> {{sia}}</div>

imported>David Eppstein