conference paper published yes Vladimir Kolmogorov author 3D50B0BA-F248-11E8-B48F-1D18A9856A87 VlKo department ICALP: Automata, Languages and Programming Discrete Optimization in Computer Vision: Theory and Practice project 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. Recent 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. https://research-explorer.ista.ac.at/download/6725/6738/2019_LIPICS_Kolmogorov.pdf application/pdfno Schloss Dagstuhl - Leibniz-Zentrum für Informatik2019Patras, Greece eng 1868-8969 978-3-95977-109-2 1803.0228910.4230/LIPICS.ICALP.2019.77 13277:1-77:12 V. Kolmogorov, “Testing the complexity of a valued CSP language,” in <i>46th International Colloquium on Automata, Languages and Programming</i>, Patras, Greece, 2019, vol. 132, p. 77:1-77:12. Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” <i>46th International Colloquium on Automata, Languages and Programming</i>, vol. 132, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12, doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2019.77">10.4230/LIPICS.ICALP.2019.77</a>. Kolmogorov, V. (2019). Testing the complexity of a valued CSP language. In <i>46th International Colloquium on Automata, Languages and Programming</i> (Vol. 132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.ICALP.2019.77">https://doi.org/10.4230/LIPICS.ICALP.2019.77</a> Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th International Colloquium on Automata, Languages and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 132, 77:1-77:12. Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” In <i>46th International Colloquium on Automata, Languages and Programming</i>, 132:77:1-77:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href="https://doi.org/10.4230/LIPICS.ICALP.2019.77">https://doi.org/10.4230/LIPICS.ICALP.2019.77</a>. Kolmogorov V. Testing the complexity of a valued CSP language. In: <i>46th International Colloquium on Automata, Languages and Programming</i>. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:77:1-77:12. doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2019.77">10.4230/LIPICS.ICALP.2019.77</a> V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12. 67252019-07-29T12:23:29Z2025-07-10T11:53:47Z