Descriptive complexity of \#P functions: a new perspective

DOI10.1016/J.JCSS.2020.04.002MaRDI QIDQ2220444zbMATH OpenOpenAlexFDO

Authors Arnaud Durand, Anselm Haak, Juha Kontinen, Heribert Vollmer

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

zbMATH Keywords

arithmetic circuitscounting classesfinite model theorySkolem function

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Descriptive complexity and finite models (68Q19)

Recommendations

• Descriptive complexity of \(\#\)P functions
• Descriptive complexity of \#AC\(^0\) functions
• scientific article; zbMATH DE number 1424025
• scientific article; zbMATH DE number 1342206
• Membrane Computing
• Descriptional complexity -- an introductory survey
• Descriptive Complexity of Function Spaces
• scientific article; zbMATH DE number 17544
• scientific article; zbMATH DE number 4106276
• Descriptive complexity of computable sequences revisited

Cites work

• A hierarchy for nondeterministic time complexity
• A logical characterization of the counting hierarchy
• 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
• Descriptive complexity for counting complexity classes
• Descriptive complexity of \(\#\)P functions
• Graph properties checkable in linear time in the number of vertices
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1351078 (Why is no real title available?)
• scientific article; zbMATH DE number 1754588 (Why is no real title available?)
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• Model-theoretic characterization of Boolean and arithmetic circuit classes of small depth
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• On uniformity within \(NC^ 1\)
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Subtractive reductions and complete problems for counting complexity classes
• The complexity of computing the permanent

Cited in

(11)

• Descriptive complexity of \(\#\)P functions
• Descriptive complexity of deterministic polylogarithmic time
• On the descriptive complexity of \(\overline{\varSigma ^*\overline{L}}\)
• scientific article; zbMATH DE number 1424025 (Why is no real title available?)
• Descriptive complexity for counting complexity classes
• Descriptive complexity for counting complexity classes
• Descriptive complexity of \#AC\(^0\) functions
• Membrane Computing
• Weighted automata and logics meet computational complexity
• Logical characterizations of weighted complexity classes
• Descriptive complexity and weighted Turing machines

This page was built for publication: Descriptive complexity of \#P functions: a new perspective

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