Implicit recursion-theoretic characterizations of counting classes

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)1129-1144
Number of pages16
JournalArchive For Mathematical Logic
Volume61
DOIs
Publication statusPublished - 2022

Keywords

  • # P
  • Counting hierarchy
  • Function algebras
  • Implicit computational complexity
  • Recursion-theoretic characterizations

Fingerprint

Dive into the research topics of 'Implicit recursion-theoretic characterizations of counting classes'. Together they form a unique fingerprint.

Cite this