Is constraint satisfaction over two variables always easy?

DOI10.1002/rsa.20026zbMath1077.68094MaRDI QIDQ3156915

Lars Engebretsen, Venkatesan Guruswami

Publication date: 12 January 2005

Published in: Random Structures and 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

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

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

68W25: Approximation algorithms

Related Items

Supermodular functions and the complexity of MAX CSP

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Outward rotations
• On the power of unique 2-prover 1-round games
• A new multilayered PCP and the hardness of hypergraph vertex cover
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming