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

From MaRDI portal
Revision as of 17:33, 29 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Generic expression hardness results for primitive positive formula comparison
scientific article

    Statements

    Generic expression hardness results for primitive positive formula comparison (English)
    0 references
    0 references
    0 references
    0 references
    6 June 2013
    0 references
    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.''
    0 references
    0 references
    primitive positive formulas
    0 references
    conjunctive queries
    0 references
    equivalence
    0 references
    computational complexity
    0 references
    clones
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references