Pergunta

A query is any mapping $I:STRUC[\sigma] \to STRUC[\tau]$ that is polynomially bounded. A boolean query is a map $I_b: STRUC[\sigma] \to \{0,1\}$. A boolean query can also be thought as the susbset: $$ \{ A \in STRUC[\sigma] \ \mid \ I_b(A) = 1 \} $$

From this definition of query, used by Immerman in his book "Descriptive Complexity", how are boolean queries and general queries related? It seems from the definition that they are two different things entirely. Is there an intuitive way to link the two concepts? Thank you!

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top