On the expression complexity of equivalence and isomorphism of primitive positive formulas

DOI10.1007/s00224-010-9302-7zbMath1288.68080MaRDI QIDQ692919

Simone Bova, Hubie Chen, Matthew A. Valeriote

Publication date: 6 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2369/

zbMATH Keywords

equivalence; computational complexity; isomorphism; clones; primitive positive formulas

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03C13: Model theory of finite structures

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, Generic expression hardness results for primitive positive formula comparison

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conjunctive query evaluation by search-tree revisited
• Universal algebra and hardness results for constraint satisfaction problems
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• Graph isomorphism is in the low hierarchy
• Constraints, consistency and closure
• On the complexity of database queries
• Conjunctive-query containment and constraint satisfaction
• Closed systems of functions and predicates
• The complexity of equivalence and isomorphism of systems of equations over finite groups
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Varieties with few subalgebras of powers
• A Subalgebra Intersection Property for Congruence Distributive Varieties
• The structure of finite algebras
• On the Structure of Polynomial Time Reducibility
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• The Formula Isomorphism Problem
• On the Hardness of Graph Isomorphism
• STACS 2004
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of satisfiability problems
• Mathematical Foundations of Computer Science 2005