scientific article; zbMATH DE number 1948177

zbMath1020.68039MaRDI QIDQ4411838

Elmar Böhler, Heribert Vollmer, Edith Hemaspaandra, Steffen Reith

Publication date: 10 July 2003

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2471/24710412.htm

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ The complexity of problems for quantified constraints ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ Isomorphic implication ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ Time Complexity of Constraint Satisfaction via Universal Algebra ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ Partial Polymorphisms and Constraint Satisfaction Problems ⋮ The complexity of equivalence and isomorphism of systems of equations over finite groups ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1 ⋮ On the isomorphism problem for decision trees and decision lists