D. Abiteboul, O. Duschka, and ;. Ahmetaj, Ontology-mediated queries: Combined complexity and succinctness of rewritings via circuit complexity, PODS, 2018. [Amarilli and Benedikt, vol.175, pp.199-217, 1998.

. Bonatti, A. Sauro-;-piero, L. Bonatti, and . Sauro, A confidentiality model for ontologies, ISWC, 2013.

, ) ? T 6 (x) They can also be produced as the result of the visible chase over one projection mapping A(x) ? T (x) with 6 Fr1LTGDs: A(x) ? R

?. ,

, General idea of the reduction The reduction that we provide will create a query Q for each instance I of Circuit SAT. Without loss of generality, we suppose that I is composed of wires w 1 , . . . , w k , of negation gates N 1