Descriptive complexity of \#P functions: a new perspective
From MaRDI portal
Publication:2220444
DOI10.1016/j.jcss.2020.04.002zbMath1467.68060OpenAlexW2345028735MaRDI QIDQ2220444
Anselm Haak, Heribert Vollmer, Juha Kontinen, Arnaud Durand
Publication date: 22 January 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10138/322725
Descriptive complexity and finite models (68Q19) Networks and circuits as models of computation; circuit complexity (68Q06)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph properties checkable in linear time in the number of vertices
- The complexity of computing the permanent
- A hierarchy for nondeterministic time complexity
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Descriptive complexity of \(\#\)P functions
- A model-theoretic characterization of constant-depth arithmetic circuits
- Subtractive reductions and complete problems for counting complexity classes
- On uniformity within \(NC^ 1\)
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Counting of Teams in First-Order Team Logics
- Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth
- A logical characterization of the counting hierarchy
