10.4230/LIPICS.ICALP.2019.77
Kolmogorov, Vladimir
Vladimir
Kolmogorov
Testing the complexity of a valued CSP language
LIPIcs
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2019
2019-07-29T12:23:29Z
2019-08-02T12:39:25Z
conference
https://research-explorer.app.ist.ac.at/record/6725
https://research-explorer.app.ist.ac.at/record/6725.json
978-3-95977-109-2
1868-8969
1803.02289
575475 bytes
application/pdf
A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language.
Recent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm, assuming that SETH holds.