The complexity of general-valued CSPs
- Submitting institution
-
University of Durham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 108193
- Type
- D - Journal article
- DOI
-
10.1137/16M1091836
- Title of journal
- SIAM Journal on Computing
- Article number
- -
- First page
- 1087
- Volume
- 46
- Issue
- 3
- ISSN
- 00975397
- Open access status
- Compliant
- Month of publication
- -
- Year of publication
- 2017
- URL
-
https://doi.org/10.1137/16M1091836
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
B - Algorithms and Complexity
- Citation count
- 16
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The paper gives a complete complexity classification for Valued CSPs (an extremely general class of mixed feasibility/optimisation problems) modulo a conjectured classification for its subclass CSP (consisting of pure feasibility problems). The conjecture for CSP has subsequently been confirmed independently by Bulatov and Zhuk (FOCS'17, shared best paper award), thus the two results together provide a full complexity classification for Valued CSPs (assuming that P is not NP). Conference version published in FOCS'15.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -