TY - JOUR

T1 - Implicit recursion-theoretic characterizations of counting classes

AU - Dal Lago, Ugo

AU - Kahle, Reinhard

AU - Oitavem, Isabel

N1 - Funding Information:
info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F00297%2F2020/PT#
The first author is supported by the ERC CoG DIAPASoN GA 818616.
The second author is supported by the same project and by the Udo Keller Foundation.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2022

Y1 - 2022

N2 - We give recursion-theoretic characterizations of the counting class # P, the class of those functions which count the number of accepting computations of non-deterministic Turing machines working in polynomial time. Moreover, we characterize in a recursion-theoretic manner all the levels {#Pk}k∈N of the counting hierarchy of functions FCH, which result from allowing queries to functions of the previous level, and FCH itself as a whole. This is done in the style of Bellantoni and Cook’s safe recursion, and it places # P in the context of implicit computational complexity. Namely, it relates # P with the implicit characterizations of FPTIME (Bellantoni and Cook, Comput Complex 2:97–110, 1992) and FPSPACE (Oitavem, Math Log Q 54(3):317–323, 2008), by exploiting the features of the tree-recursion scheme of FPSPACE.

AB - We give recursion-theoretic characterizations of the counting class # P, the class of those functions which count the number of accepting computations of non-deterministic Turing machines working in polynomial time. Moreover, we characterize in a recursion-theoretic manner all the levels {#Pk}k∈N of the counting hierarchy of functions FCH, which result from allowing queries to functions of the previous level, and FCH itself as a whole. This is done in the style of Bellantoni and Cook’s safe recursion, and it places # P in the context of implicit computational complexity. Namely, it relates # P with the implicit characterizations of FPTIME (Bellantoni and Cook, Comput Complex 2:97–110, 1992) and FPSPACE (Oitavem, Math Log Q 54(3):317–323, 2008), by exploiting the features of the tree-recursion scheme of FPSPACE.

KW - # P

KW - Counting hierarchy

KW - Function algebras

KW - Implicit computational complexity

KW - Recursion-theoretic characterizations

UR - http://www.scopus.com/inward/record.url?scp=85129338124&partnerID=8YFLogxK

U2 - 10.1007/s00153-022-00828-4

DO - 10.1007/s00153-022-00828-4

M3 - Article

AN - SCOPUS:85129338124

VL - 61

SP - 1129

EP - 1144

JO - Archive For Mathematical Logic

JF - Archive For Mathematical Logic

SN - 0933-5846

ER -