Descriptive complexity for counting complexity classes

MaRDI QIDQ5144698zbMATH OpenFDO

Authors Marcelo Arenas, Martín Muñoz, Cristian Riveros

Publication date 19 January 2021

Full work available at URL http://dl.acm.org/citation.cfm?id=3330085

Mathematics Subject Classification ID

Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Descriptive complexity for counting complexity classes
• Descriptive complexity of \(\#\)P functions
• Descriptive complexity of \#P functions: a new perspective
• Descriptive complexity of \#AC\(^0\) functions
• Complexity classes defined by counting quantifiers

Cited in

(11)

• Descriptive complexity of \(\#\)P functions
• Completeness, approximability and exponential time results for counting problems with easy decision version
• Descriptive complexity of \#P functions: a new perspective
• Descriptive Complexity of approximate counting CSPs
• Pumping lemmas for weighted automata
• Counting of Teams in First-Order Team Logics
• DESCRIPTIVE COMPLEXITY IN CANTOR SERIES
• Descriptive complexity for counting complexity classes
• On counting propositional logic and Wagner's hierarchy
• Weighted automata and logics meet computational complexity
• Counting of teams in first-order team logics

This page was built for publication: Descriptive complexity for counting complexity classes

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