2014/06/12 by Peter Jönsson, Victor Lagerkvist, Jonsson, Peter +6
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Formal Methods in Verification #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1406.3247
openalex publication_date 2014/06/12 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Obtaining lower bounds for NP-hard problems has for a long time been an\nactive area of research. Recent algebraic techniques introduced by Jonsson et\nal. (SODA 2013) show that the time complexity of the parameterized SAT(\⋅)\nproblem correlates to the lattice of strong partial clones. With this ordering\nthey isolated a relation R such that SAT(R) can be solved at least as fast\nas any other NP-hard SAT(\⋅) problem. In this paper we extend this method\nand show that such languages also exist for the max ones problem\n(MaxOnes(\Γ)) and the Boolean valued constraint satisfaction problem over\nfinite-valued constraint languages (VCSP(\Δ)). With the help of these\nlanguages we relate MaxOnes and VCSP to the exponential time hypothesis in\nseveral different ways.\n