Some observations on the connection between counting and recursion (Q1098837): Difference between revisions

Let {\#}P be the \textit{L. G. Valiant}'s [ibid. 8, 189-201 (1979; Zbl 0415.68008)] class of all functions counting the number of accepting paths in nondeterministic polynomial-time computations. The author introduces the polynomial-time hierarchy of functions by defining 0{\#}P\(=P\) and \((k+I)\#P\) to be the class of all functions counting the number of accepting paths of nondeterminisitic polynomial-time machines which have a function from k{\#}P as an oracle (thus I{\#}P\(=\#P)\). For \(PHCF=\cup \{k\#P:\) \(k\geq 0\}\) the following inclusions take place: \[ P\subseteq 0\#P\subseteq I\#P\subseteq...\subseteq PHCF\subseteq PSPACE. \] PHCF is shown to be coincident with the closure of the class P with respect to the operations of substitution and summation. The class PHCF can be generated from the basic functions \(\{+,-,\cdot,:\}\) by substitution, weak bounded primitive recursion and weak product (weak here means ``up to the length of the argument on which the recursion is made'').