STACS 2004

DOI10.1007/B96012MaRDI QIDQ5309697zbMATH OpenOpenAlexFDO

Authors Elmar Böhler, Edith Hemaspaandra, Heribert Vollmer, S. Reith

Publication date 1 October 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b96012

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• scientific article; zbMATH DE number 1948177
• Complexity classifications of Boolean constraint satisfaction problems
• Isomorphic implication
• Mathematical Foundations of Computer Science 2005
• On the computational complexity of some classical equivalence relations on boolean functions

Cited in

(12)

• Bases for Boolean co-clones
• Isomorphic implication
• On the isomorphism problem for decision trees and decision lists
• The complexity of equivalence and isomorphism of systems of equations over finite groups
• Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF
• Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
• On the expression complexity of equivalence and isomorphism of primitive positive formulas

This page was built for publication: STACS 2004

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5309697)