Generic expression hardness results for primitive positive formula comparison Journal Articles

abstract

• We study the expression complexity of two basic problems involving the comparison of primitive positive formulas: equivalence and containment. In particular, we study the complexity of these problems relative to finite relational structures. We present two generic hardness results for the studied problems, and discuss evidence that they are optimal and yield, for each of the problems, a complexity trichotomy.

authors

• Bova, Simone
• Chen, Hubie
• Valeriote, Matthew Anthony

status

• published 

publication date

• January 2013

has subject area

• 08 Information and Computing Sciences (FoR)
• Computation Theory & Mathematics (Science Metrix)

published in

• Information and Computation  Journal

keywords

• ALGEBRAS
• COMPLEXITY
• CONSTRAINT SATISFACTION PROBLEMS
• Clones
• Computational complexity
• Computer Science
• Computer Science, Theory & Methods
• Conjunctive queries
• Equivalence
• Mathematics
• Mathematics, Applied
• Physical Sciences
• Primitive positive formulas
• Science & Technology
• Technology
• VARIETIES

Digital Object Identifier (DOI)

• 10.1016/j.ic.2012.10.008

start page

• 108

end page

• 120

volume

• 222