Can I read Testing the complexity of a valued CSP language on EtoBox?

Testing the complexity of a valued CSP language by Kolmogorov, Vladimir is a scholarly article available to read on EtoBox.

What is Testing the complexity of a valued CSP language about?

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 $\Gamma$ of cost functions, called a language. Recent breakthrough results have established a complete complexity classification of such classes with respect to language $\Gamma$: if all cost functions in $\Gamma$ satisfy a certain algebraic condition then all $\Gamma$-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language $\Gamma$ 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 $\Gamma$ can be tested in $O(\sqrt[3]{3}^{\,|D|}\cdot poly(size(\Gamma)))$ time, where $D$ is the domain of $\Gamma$ and $poly(\cdot)$ is some fixed polynomial

Author

Kolmogorov, Vladimir

Published

2018

Language

EN