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.
We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH).
More precisely, we prove that for any constant $\delta < 1$ there is no $O(\sqrt[3]{3}^{\,\delta|D|})$
algorithm, assuming that SETH holds.