Is constraint satisfaction over two variables always easy?

DOI10.1002/RSA.20026MaRDI QIDQ3156915zbMATH OpenOpenAlexFDO

Authors Lars Engebretsen, Venkatesan Guruswami

Publication date 12 January 2005

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20026

zbMATH Keywords

Not-All-Equal Sat

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 2019637
• Why almost all satisfiable k-CNF formulas are easy
• Constraint satisfaction problems: convexity makes AllDifferent constraints tractable
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Sparsification of two-variable valued constraint satisfaction problems
• Constraint Satisfaction
• scientific article; zbMATH DE number 1008453
• Artificial Intelligence: Methodology, Systems, and Applications
• A new algorithm for optimal 2-constraint satisfaction and its implications

Cites work

• A new multilayered {PCP} and the hardness of hypergraph vertex cover
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• scientific article; zbMATH DE number 3577438 (Why is no real title available?)
• scientific article; zbMATH DE number 1304324 (Why is no real title available?)
• On the power of unique 2-prover 1-round games
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems

Cited in

(10)

• Supermodular functions and the complexity of MAX CSP
• Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^{n}\)
• On the NP-hardness of Max-Not-2
• Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^n\)
• scientific article; zbMATH DE number 2019637 (Why is no real title available?)
• The Nonapproximability of Non-Boolean Predicates
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• (2+)-Sat is NP-hard
• On the NP-hardness of MAX-Not-2

Describes a project that uses

Uses Software

• Outward rotations

This page was built for publication: Is constraint satisfaction over two variables always easy?

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