Consulta (complejidad)
En complejidad descriptiva , una consulta es un mapeo de estructuras de una firma a estructuras de otro vocabulario. Neil Immerman , en su libro Descriptive Complexity, [1] "utiliza el concepto de consulta como el paradigma fundamental de la computación" (p. 17).
Dadas las firmas y , definimos el conjunto de estructuras en cada idioma, y . Una consulta es entonces cualquier mapeo
![{\mbox{STRUC}}[\sigma]](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbb1b6cb871373070d84dfce92ff90adbb971515)
![{\mbox{STRUC}}[\tau]](https://wikimedia.org/api/rest_v1/media/math/render/svg/b84dfe41dfb6a45d27366be7dce3a2ee81fdc42f)
![Yo:{\mbox{STRUC}}[\sigma ]\to {\mbox{STRUC}}[\tau ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/816a8508c68f407dacb4842779a3c229b3a3fd69)
La teoría de la complejidad computacional puede entonces expresarse en términos del poder de la lógica matemática necesaria para expresar una consulta determinada.
Una consulta es independiente del orden si el orden de los objetos en la estructura no afecta los resultados de la consulta. En las bases de datos, estas consultas corresponden a consultas genéricas (Immerman 1999, p. 18). Una consulta es iff independiente del orden para cualquier estructura isomorfa y .
