Domanda

UN Domanda è una mappatura $ I: struc [ sigma] a struc [ tau] $ Questo è il limite polinomia. UN booleano La query è una mappa $ I_b: struc [ sigma] to {0,1 } $. Una query booleana può anche essere pensata come la Susbet: $$ {a in struc [ sigma] mid i_b (a) = 1 } $$

Da questa definizione di query, usata da immerman nel suo libro "complessità descrittiva", come sono correlate le domande booleane e le domande generali? Dalla definizione sembra che siano completamente due cose diverse. Esiste un modo intuitivo per collegare i due concetti? Grazie!

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top