Descriptive complexity of \(\#\)P functions

DOI10.1006/jcss.1995.1039zbMath0837.68034OpenAlexW2061042466MaRDI QIDQ1894456

Sanjeev Saluja, K. V. Subrahmanyam, Madhukar N. Thakur

Publication date: 29 April 1996

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1039

zbMATH Keywords

counting problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Completeness Results for Counting Problems with Easy Decision ⋮ Unnamed Item ⋮ On the connection between interval size functions and path counting ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Descriptive complexity of \#P functions: a new perspective ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ A model-theoretic characterization of constant-depth arithmetic circuits ⋮ The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws ⋮ An Experimental Study of the Treewidth of Real-World Graph Data ⋮ Counting of Teams in First-Order Team Logics ⋮ Counting problems over the reals ⋮ Subtractive reductions and complete problems for counting complexity classes

This page was built for publication: Descriptive complexity of \(\#\)P functions