Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
Peter Jönsson, Victor Lagerkvist, Johannes Schmidt, Hannes Uppman · arXiv (Cornell University) · 2014
Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the time complexity of the parameterized SAT($\cdot$) problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation $R$ such that SAT($R$) can be solved at least as fast as any other NP-hard SAT($\cdot$) problem. In this paper we extend this method and show that such languages also exist for the max ones problem (MaxOnes($Γ$)) and the Boolean valued constraint satisfaction problem over finite-valued constraint languages (VCSP($Δ$)). With the help of these languages we relate MaxOnes and VCSP to the exponential time hypothesis in several different ways.