Hard constraint satisfaction problems have hard gaps at location 1

DOI10.1016/j.tcs.2009.05.022zbMath1176.90498OpenAlexW2029110781MaRDI QIDQ837178

Fredrik Kuivinen, Peter Jonsson, Andrei A. Krokhin

Publication date: 10 September 2009

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.022

zbMATH Keywords

computational complexityoptimisationconstraint satisfactiondichotomyuniversal algebraapproximability

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Strong partial clones and the time complexity of SAT problems ⋮ PTAS for Sparse General-valued CSPs ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ The Power of Linear Programming for General-Valued CSPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of constraint satisfaction games and QCSP
• List homomorphisms of graphs with bounded degrees
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• A dichotomy theorem for maximum generalized satisfiability problems.
• Existence theorems for weakly symmetric operations
• Ramanujan graphs
• Optimization, approximation, and complexity classes
• On the algebraic structure of combinatorial problems
• The hardness of approximation: Gap location
• Learnability of quantified formulas.
• Some APX-completeness results for cubic graphs
• The complexity of solving equations over finite groups
• Inapproximability results for equations over finite groups
• Supermodular functions and the complexity of MAX CSP
• The Approximability of Constraint Satisfaction Problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Near-optimal algorithms for unique games
• Complexity of conservative constraint satisfaction problems
• Proof verification and the hardness of approximation problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The approximability of MAX CSP with fixed-value constraints
• Maximum Constraint Satisfaction on Diamonds
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• On the power of unique 2-prover 1-round games
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Probabilistic checking of proofs
• Applications of a Planar Separator Theorem
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• On the Structure of Polynomial Time Reducibility
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• The Approximability of Three-valued MAX CSP
• A Simple Algorithm for Mal'tsev Constraints
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• The PCP theorem by gap amplification

This page was built for publication: Hard constraint satisfaction problems have hard gaps at location 1