Descriptive Complexity of approximate counting CSPs

DOI10.4230/LIPICS.CSL.2013.149MaRDI QIDQ2958520zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov, Víctor Dalmau, Marc Thurley

Publication date 2 February 2017

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2013/4195/pdf/15.pdf

zbMATH Keywords

approximate countingconstraint satisfaction problemsdescriptive complexity

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19)

Recommendations

• Descriptive complexity for counting complexity classes
• Descriptive complexity for counting complexity classes
• The complexity of approximating conservative counting CSPs
• The complexity of approximating conservative counting CSPs
• The relative complexity of approximate counting problems
• scientific article; zbMATH DE number 1670534
• On the parameterized complexity of approximate counting
• Approximate counting and NP search problems
• The complexity of counting \(\mathrm{CSP}^d\)
• scientific article; zbMATH DE number 1342206

Cited in

(3)

• Approximate Counting CSP Seen from the Other Side
• Approximate counting and NP search problems
• scientific article; zbMATH DE number 7561704 (Why is no real title available?)

This page was built for publication: Descriptive Complexity of approximate counting CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2958520)