On the Hamming distance of constraint satisfaction problems.

DOI10.1016/S0304-3975(01)00146-3zbMath1061.68070MaRDI QIDQ1853512

Pierluigi Crescenzi, Gianluca Rossi

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

SatisfiabilityComputational complexityApproximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (4)

Leprechauns on the chessboard ⋮ Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems ⋮ As Close as It Gets ⋮ Minimal distance of propositional models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completeness in approximation classes
• Optimization, approximation, and complexity classes
• The Approximability of Constraint Satisfaction Problems
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

This page was built for publication: On the Hamming distance of constraint satisfaction problems.