2026-07-23T18:08:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10653 2024-03-06T10:46:23Z ddc:004 open_access

Testing the Complexity of a Valued CSP Language Kolmogorov, Vladimir Valued Constraint Satisfaction Problems Exponential time algorithms Exponential Time Hypothesis 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|}* poly(size(Gamma))) time, where D is the domain of Gamma 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 delta<1 there is no O(sqrt[3]{3}^{delta|D|}) algorithm, assuming that SETH holds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vladimir Kolmogorov 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.77 urn:nbn:de:0030-drops-106531 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.77 eng https://creativecommons.org/licenses/by/3.0/legalcode