On the Pi-2-P Completeness of the Containment Problem of Conjunctive Queries with Negation and Other Problems
Abstract
This research note proves the $\Pi_2^P$-completeness of several equivalent problems: deduction in the first-order logical fragment composed of existential conjunctive formulas, deduction in polarized graphs (which are simple conceptual graphs with negation on relations, built on a simplified vocabulary) and containment of conjunctive queries with negation. The exhibited reduction is essentially due to Guillaume Bagan (November 2004).