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

DOI10.1007/S00224-010-9302-7MaRDI QIDQ692919zbMATH OpenOpenAlexFDO

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/

zbMATH Keywords

computational complexityequivalenceisomorphismclonesprimitive 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)

Recommendations

• Polynomial equivalence of the problems ``predicate formulas isomorphism and graph isomorphism
• Mathematical Foundations of Computer Science 2003
• Decidability of definability

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 139656 (Why is no real title available?)
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)
• scientific article; zbMATH DE number 3336786 (Why is no real title available?)
• A Subalgebra Intersection Property for Congruence Distributive Varieties
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Classifying the Complexity of Constraints Using Finite Algebras
• Closed systems of functions and predicates
• Complexity classifications of Boolean constraint satisfaction problems
• Conjunctive query evaluation by search-tree revisited
• Conjunctive-query containment and constraint satisfaction
• Constraints, consistency and closure
• Does co-NP have short interactive proofs ?
• Graph isomorphism is in the low hierarchy
• Mathematical Foundations of Computer Science 2005
• On the Hardness of Graph Isomorphism
• On the Structure of Polynomial Time Reducibility
• On the complexity of database queries
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• STACS 2004
• The Formula Isomorphism Problem
• The complexity of equivalence and isomorphism of systems of equations over finite groups
• The complexity of satisfiability problems
• The complexity of satisfiability problems: Refining Schaefer's theorem
• The structure of finite algebras
• Tractability and learnability arising from algebras with few subpowers
• Universal algebra and hardness results for constraint satisfaction problems
• Varieties with few subalgebras of powers

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)