Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Algebraic techniques introduced by Jonsson et al. (2017) [4] show that the fine-grained time complexity of the parameterized problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that can be solved at least as fast as any other NP-hard problem. In this paper we extend this method and show that such languages also exist for the surjective SAT problem, the max ones problem, the propositional abduction problem, and the Boolean valued constraint satisfaction problem over finite-valued constraint languages. These languages may be interesting when investigating the borderline between polynomial time, subexponential time and exponential-time algorithms since they in a precise sense can be regarded as NP-hard problems with minimum time complexity. Indeed, with the help of these languages we relate all of the above problems to the exponential time hypothesis (ETH) in several different ways.

In this paper we study the computational complexity of the extended minimum cost homomorphism problem (Min-Cost-Hom) as a function of a constraint language, i.e. a set of constraint relations and cost functions that are allowed to appear in instances. A wide range of natural combinatorial optimisation problems can be expressed as extended Min-Cost-Homs and a classification of their complexity would be highly desirable, both from a direct, applied point of view as well as from a theoretical perspective. The extended Min-Cost-Hom can be understood either as a flexible optimisation version of the constraint satisfaction problem (CSP) or a restriction of the (general-valued) valued constraint satisfaction problem (VCSP). Other optimisation versions of CSPs such as the minimum solution problem (Min-Sol) and the minimum ones problem (Min-Ones) are special cases of the extended Min-Cost-Hom. The study of VCSPs has recently seen remarkable progress. A complete classification for the complexity of finite-valued languages on arbitrary finite domains has been obtained in [Thapper and Zivny, STOC'13]. However, understanding the complexity of languages that are not finite-valued appears to be more difficult. The extended Min-Cost-Hom allows us to study problematic languages of this type without having to deal with with the full generality of the VCSP. A recent classification for the complexity of three-element by Min-Sol [Uppman, ICALP'13], takes a step in this direction. In this paper we generalise this result considerably by determining the complexity of three-element extended Min-Cost-Hom.