Implicit recursion-theoretic characterizations of counting classes
type: Item
instance of: scholarly article
title: Implicit recursion-theoretic characterizations of counting classes
zbMATH Open document ID: 1506.03096
author: Ugo Dal Lago
author: Reinhard Kahle
author: Isabel Oitavem
published in: Archive for Mathematical Logic
publication date: 2022-10-18T00:00:00Z
review text: \textit{L. G. Valiant} [Theor. Comput. Sci. 8, 189--201 (1979; Zbl 0415.68008)] introduced the class \(\#P\) of all functions which count the number of accepting computations of non-deterministic Turing machines working in polynomial time. Later \textit{K. W. Wagner} [Theor. Comput. Sci. 47, 131--147 (1986; Zbl 0637.03034)] introduced a hierarchy of counting functions FCH by allowing queries to functions of the previous level as follows: the level \(0\) coincides with the class of functions FPTIME introduced by \textit{S. Bellantoni} and \textit{S. Cook} [Comput. Complexity 2, No. 2, 97--110 (1992; Zbl 0766.68037)], and for \(k>0\), \(\# P_k=(\#P)^{\#P_{k-1}}\), FCH =\(\bigcup_{k\ge 0}\{\# P_k\}\). In particular, \(\# P_1=\#P\). Here for classes of functions \(\mathcal{F}\) and \(\mathcal{G}\), \(\mathcal{F}^{\mathcal{G}}\) denotes the class of all functions which can be computed with \(\mathcal{F}\) resources but allowing oracle access to functions from \(\mathcal{G}\). \par In the paper under review, the authors give recursion-theoretic characterizations of all the levels \(\{\# P_k\}_{k\in \mathbb{N}}\), and of FCH itself.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 7603660
zbMATH Keywords: counting hierarchy
zbMATH Keywords: implicit computational complexity
zbMATH Keywords: function algebras
zbMATH Keywords: recursion-theoretic characterizations
reviewed by: M. M. Arslanov
MaRDI profile type: Publication
full work available at URL: s00153-022-00828-4
OpenAlex ID: W4225321823
cites work: A new recursion-theoretic characterization of the polytime functions
cites work: Separating NC along the \(\delta\) axis
cites work: Monotonicity constraints in characterizations of PSPACE
cites work: Polytime, combinatory logic and positive safe induction
cites work: Q5586401
cites work: Q6168449
cites work: Q3487327
cites work: The power of the middle bit of a \(\#\)P function
cites work: Applicative theories for the polynomial hierarchy of time and its levels
cites work: Q4850553
cites work: Characterizing NC with tier 0 pointers
cites work: Characterizing PSPACE with pointers
cites work: A recursion-theoretic approach to NP
cites work: The polynomial hierarchy of functions and its levels
cites work: The realm of primitive recursion
cites work: Theories with self-application and computational complexity.
cites work: Q3081651
cites work: The complexity of computing the permanent
cites work: Recursion theoretic characterizations of complexity classes of counting functions
cites work: Some observations on the connection between counting and recursion
DOI: 10.1007/S00153-022-00828-4
description: scientific article; zbMATH DE number 7603660