Is constraint satisfaction over two variables always easy?

DOI10.1002/rsa.20026zbMath1077.68094OpenAlexW2097646889MaRDI 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

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

Related Items (2)

Supermodular functions and the complexity of MAX CSP ⋮ Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

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

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