Query (complexity)

In <a href="/facts/Descriptive_complexity/Ec5F9CnT">descriptive complexity</a>, a query is a mapping from structures of one <a href="/facts/Signature_(logic)/C0YQCuce">signature</a> to structures of another vocabulary. <a href="/facts/Neil_Immerman/7aCupltL">Neil Immerman</a>, in his book Descriptive Complexity, "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).
Given signatures 
 
 
 
 σ
 
 
 {\displaystyle \sigma }
 
 and 
 
 
 
 τ
 
 
 {\displaystyle \tau }
 
, we define the set of <a href="/facts/Structure_(mathematical_logic)/GsMx1fEb">structures</a> on each language, 
 
 
 
 
 
 STRUC
 
 
 [
 σ
 ]
 
 
 {\displaystyle {\mbox{STRUC}}[\sigma ]}
 
 and 
 
 
 
 
 
 STRUC
 
 
 [
 τ
 ]
 
 
 {\displaystyle {\mbox{STRUC}}[\tau ]}
 
. A query is then any mapping

<blockquote>

 
 
 
 I
 :
 
 
 STRUC
 
 
 [
 σ
 ]
 →
 
 
 STRUC
 
 
 [
 τ
 ]
 
 
 {\displaystyle I:{\mbox{STRUC}}[\sigma ]\to {\mbox{STRUC}}[\tau ]}

</blockquote>
<a href="/facts/Computational_complexity_theory/etHuVF3U">Computational complexity theory</a> can then be phrased in terms of the power of the mathematical logic necessary to express a given query.

Query (complexity) open-in-new

Query (complexity)