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

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

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)

• Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
• On the expression complexity of equivalence and isomorphism of primitive positive formulas
• Bases for Boolean co-clones
• On the isomorphism problem for decision trees and decision lists
• The complexity of equivalence and isomorphism of systems of equations over finite groups
• Isomorphic implication
• Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF
• 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?

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)