As Close as It Gets

DOI10.1007/978-3-319-30139-6_18zbMath1475.68217MaRDI QIDQ2803825

Miki Hermann, Stefan Mengel, Gernot Salzer, Mike Behrisch

Publication date: 3 May 2016

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-30139-6_18

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

90C09: Boolean programming

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68R07: Computational aspects of satisfiability

Related Items

Time Complexity of Constraint Satisfaction via Universal Algebra, Unnamed Item, The Next Whisky Bar, Minimal distance of propositional models

Cites Work

• Unnamed Item
• Unnamed Item
• Bases for Boolean co-clones
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On the Hamming distance of constraint satisfaction problems.
• Weak bases of Boolean co-clones
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Give Me Another One!
• Closure properties of constraints
• Hardness of approximating the minimum distance of a linear code
• The complexity of satisfiability problems
• Partial Polymorphisms and Constraint Satisfaction Problems
• A Theorem on Boolean Matrices