  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.
