---
_id: '6725'
abstract:
- lang: eng
  text: "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. \r\nRecent 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."
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: '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>'
  apa: '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>'
  chicago: 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>.
  ieee: 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.
  ista: '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.'
  mla: 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>.
  short: V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages
    and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12.
conference:
  end_date: 2019-07-12
  location: Patras, Greece
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 2019-07-08
date_created: 2019-07-29T12:23:29Z
date_published: 2019-07-01T00:00:00Z
date_updated: 2025-07-10T11:53:47Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.4230/LIPICS.ICALP.2019.77
ec_funded: 1
external_id:
  arxiv:
  - '1803.02289'
file:
- access_level: open_access
  checksum: f5ebee8eec6ae09e30365578ee63a492
  content_type: application/pdf
  creator: dernst
  date_created: 2019-07-31T07:01:45Z
  date_updated: 2020-07-14T12:47:38Z
  file_id: '6738'
  file_name: 2019_LIPICS_Kolmogorov.pdf
  file_size: 575475
  relation: main_file
file_date_updated: 2020-07-14T12:47:38Z
has_accepted_license: '1'
intvolume: '       132'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 77:1-77:12
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: 46th International Colloquium on Automata, Languages and Programming
publication_identifier:
  isbn:
  - 978-3-95977-109-2
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Testing the complexity of a valued CSP language
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 132
year: '2019'
...