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

DOI10.1007/s00224-010-9302-7zbMath1288.68080OpenAlexW2032976034MaRDI 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

equivalencecomputational complexityisomorphismclonesprimitive positive formulas

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

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

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

This page was built for publication: On the expression complexity of equivalence and isomorphism of primitive positive formulas