STACS 2004

DOI10.1007/B96012MaRDI QIDQ5309697zbMATHOpenAlexFDO

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

(11)

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

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)