On the expression complexity of equivalence and isomorphism of primitive positive formulas
From MaRDI portal
Publication:692919
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/
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
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