On the expression complexity of equivalence and isomorphism of primitive positive formulas
DOI10.1007/S00224-010-9302-7zbMATH Open1288.68080OpenAlexW2032976034MaRDI QIDQ692919FDOQ692919
Authors: Simone Bova, Hubie Chen, Matthew 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/
Recommendations
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)
Cites Work
- Complexity classifications of Boolean constraint satisfaction problems
- Varieties with few subalgebras of powers
- On the Structure of Polynomial Time Reducibility
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- On the Hardness of Graph Isomorphism
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Constraints, consistency and closure
- Conjunctive-query containment and constraint satisfaction
- Title not available (Why is that?)
- The structure of finite algebras
- Tractability and learnability arising from algebras with few subpowers
- Closed systems of functions and predicates
- Title not available (Why is that?)
- Title not available (Why is that?)
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- Mathematical Foundations of Computer Science 2005
- Universal algebra and hardness results for constraint satisfaction problems
- Graph isomorphism is in the low hierarchy
- A Subalgebra Intersection Property for Congruence Distributive Varieties
- On the complexity of database queries
- The Formula Isomorphism Problem
- Title not available (Why is that?)
- The complexity of satisfiability problems: Refining Schaefer's theorem
- The complexity of equivalence and isomorphism of systems of equations over finite groups
- Title not available (Why is that?)
- STACS 2004
- Conjunctive query evaluation by search-tree revisited
Cited In (6)
- The power of primitive positive definitions with polynomially many variables
- Decidability of definability
- The reducts of equality up to primitive positive interdefinability
- Learnability of solutions to conjunctive queries
- Polynomial equivalence of the problems ``predicate formulas isomorphism and graph isomorphism
- Two-element structures modulo primitive positive constructability
This page was built for publication: On the expression complexity of equivalence and isomorphism of primitive positive formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692919)
