Comment comprendre la notion de requête booléenne via la définition d'Immerman
-
05-11-2019 - |
Question
UN requête est toute cartographie $ I: struc [ sigma] to struc [ tau] $ qui est limité polynomialement. UN booléen La requête est une carte $ I_b: struc [ sigma] à {0,1 } $. Une requête booléenne peut également être considérée comme le Susbset: $$ {a in struc [ sigma] mid i_b (a) = 1 } $$
À partir de cette définition de la requête, utilisée par Immerman dans son livre "Descriptive Complexity", comment les requêtes booléennes et les requêtes générales sont-elles liées? Il semble d'après la définition qu'ils sont entièrement deux choses différentes. Existe-t-il un moyen intuitif de relier les deux concepts? Merci!
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange