---
res:
bibo_abstract:
- "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. \r\nRecent 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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Vladimir
foaf_name: Kolmogorov, Vladimir
foaf_surname: Kolmogorov
foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.4230/LIPICS.ICALP.2019.77
bibo_volume: 132
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/1868-8969
- http://id.crossref.org/issn/978-3-95977-109-2
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Testing the complexity of a valued CSP language@
...