The complexity of approximating conservative counting CSPs
- Submitting institution
-
The University of Leeds
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- UOA11-96
- Type
- D - Journal article
- DOI
-
10.1016/j.jcss.2014.06.006
- Title of journal
- Journal of Computer and System Sciences
- Article number
- -
- First page
- 311
- Volume
- 81
- Issue
- 1
- ISSN
- 0022-0000
- Open access status
- Out of scope for open access requirements
- Month of publication
- June
- Year of publication
- 2014
- URL
-
-
- 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
-
6
- Research group(s)
-
A - AC (Algorithms and Complexity)
- Citation count
- 7
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- CSPs are a widely-used model of computation that avoids the undecidability of Turing machine computation. The counting CSP asks how many solutions exist to a CSP. The complexity of exact counting was completely settled by a dichotomy theorem of Bulatov and of Dyer and Richerby. Problems are either in polynomial time, or are #P-Complete. Whether similar results hold for the complexity of approximate counting is then an important theoretical question. This paper answers that question partly, but shows that the general picture is far more complicated than for exact counting. However, it also gives some satisfactory answers for special cases.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
