Generic expression hardness results for primitive positive formula comparison (Q1951576)

A primitive positive formula is a first-order formula defined from atomic formulas and equality of variables using conjunction and existential quantification. These formulas are equivalent to conjunctive queries. The authors study the complexity of the following two problems for given primitive positive formulas \(\varphi\) and \(\psi\) over a finite relational structure: -- Equivalence problem: are \(\varphi\) and \(\psi\) equivalent, i.e., do they have the same satisfying assignment? -- Containment problem: are the satisfying assignments of \(\varphi\) contained in those of \(\psi\)? These computational problems are studied with respect to various fixed (finite) structures. The authors' suggestion is that ``various relational structures -- which may represent databases or knowledge bases, according to use -- may possess structural characteristics that affect the complexity of the resulting problems'' and the authors are interested in ``understanding this interplay''. For a finite relational structure \(\bar{B}\) with the universe \(B\) let \(\text{A}_{\bar{B}}\) denote the (finite) algebra \(\langle B,{\mathtt Pol}(\bar{B})\rangle\) where \({\mathtt Pol}(\bar{B})\) is the set of all polymorphisms of \({B}\), i.e., the set of all operations on \(B\) that preserve the relations of \(\bar{B}\). The two main results of the paper are: (1) For any finite relational ``structure \(\bar{B}\) whose associated algebra \(\text{A}_{\bar{B}}\) gives rise to a variety \({\mathcal V}(\text{A}_{\bar{B}})\) that admits the unary type, both the equivalence and containment problem are \(\Pi_2^p\)-hard. Note that this is the maximal complexity possible for these problems, as the problems are contained in the class \(\Pi_2^p\).'' (2) For any finite relational ``structure \(\bar{B}\) if the variety \({\mathcal V}(\text{A}_{\bar{B}})\) is not congruence modular, then the equivalence and containment problems are coNP-hard.''