Some observations on the connection between counting and recursion (Q1098837): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(86)90141-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2002385864 / rank | |||
Normal rank |
Revision as of 22:43, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some observations on the connection between counting and recursion |
scientific article |
Statements
Some observations on the connection between counting and recursion (English)
0 references
1986
0 references
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'').
0 references
counting functions
0 references
accepting paths
0 references
nondeterministic polynomial-time computations
0 references
polynomial-time hierarchy of functions
0 references
oracle
0 references