# Some Observations on the Connection Between Counting an Recursion

@article{Wagner1986SomeOO, title={Some Observations on the Connection Between Counting an Recursion}, author={Klaus W. Wagner}, journal={Theor. Comput. Sci.}, year={1986}, volume={47}, pages={131-147} }

Abstract Based on Valiant's class # P of all functions counting the number of accepting computations of nondeterministic polynomial-time Turing machines, the polynomial-time hierarchy of counting functions is introduced. The class PHCF of all functions of this hierarchy and some of its subclasses are characterized by recursion-theoretic means. It turns out that, from the recursion-theoretic point of view, PHCF is an analogue to Kalmar's class E of elementary functions, to the class Pspace of… Expand

#### Topics from this paper

#### 52 Citations

On Counting and Approximation

- Mathematics, Computer Science
- CAAP
- 1988

We introduce a new class of functions, called span functions which count the different output values that occur at the leaves of the computation tree associated with a nondeterministic polynomial… Expand

Recursion Theoretic Characterizations of Complexity Classes of Counting Functions

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1996

The hierarchy of counting functions, which is the closure of #P under substitution, is characterized, remarkably without using the operator of substitution, since it is shown that in the context of this hierarchy the operation of modified subtraction is as powerful as substitution. Expand

On counting and approximation

- Computer Science
- Acta Informatica
- 2004

A probabilistic approximation method is presented to approximate span functions up to any desired degree of accuracy, based on universal hashing and it never underestimates the correct value of the approximated function. Expand

Enumerative Counting Is Hard

- Computer Science, Mathematics
- Inf. Comput.
- 1989

It is proved that if there is a good polynomial-time enumerator for #P (i.e., one where for every Boolean formula f, the small set has at most O(|f|1−e) numbers), then P = NP = P# P and probabilisticPolynomial time equals polynometric time. Expand

The Complexity of Finding Middle Elements

- Mathematics, Computer Science
- Int. J. Found. Comput. Sci.
- 1993

Two related classes of functions that yield the middle element in the ordered sequence of output values of nondeterministic polynomial time Turing machines are defined and the inclusion structure between these classes is determined. Expand

Enumerative counting is hard

- Mathematics, Computer Science
- [1988] Proceedings. Structure in Complexity Theory Third Annual Conference
- 1988

It is proved that if there is a good polynomial-time enumerator for Hash P (i.e. one where the small set has at most O( mod f mod /sup 1-e/) numbers), then P=NP=P/sup Hash P/ and probabilisticPolynomial time equals polynometric time. Expand

Relations Among Parallel and Sequential Computation Models

- Computer Science
- ASIAN
- 1996

This paper relates uniform small-depth circuit families as a parallel computation model with the complexity of polynomial time Turing machines. Among the consequences we obtain are: (a) a collapse of… Expand

On the power of number-theoretic operations with respect to counting

- Mathematics, Computer Science
- Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference
- 1995

This work investigates function classes /sub f/ which are defined as the closure of P under the operation f and a set of known closure properties of P, e.g. summation over an exponential range and calls these operations counting hard and gives general criteria for hardness. Expand

The power of counting

- Mathematics, Computer Science
- [1988] Proceedings. Structure in Complexity Theory Third Annual Conference
- 1988

An overview of applications and variations of counting in structural complexity theory is provided. It is argued that the capacity for exact counting is closely related with the capacity for… Expand

On Type-2 Probabilistic Quantifiers

- Computer Science
- ICALP
- 1996

This work defines and examines several probabilistic operators ranging over sets (i.e., operators of type 2), among others the formerly studied ALMOST-operator, and proves that they all coincide for a wide variety of classes. Expand

#### References

SHOWING 1-10 OF 19 REFERENCES

Two remarks on the power of counting

- Mathematics
- 1983

The relationship between the polynomial hierarchy and Valiant's class #P is at present unknown. We show that some low portions of the polynomial hierarchy, namely deterministic polynomial algorithms… Expand

On Counting Problems and the Polynomial-Time Hierarchy

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1980

The main result is that there exists an oracle set A such that PPA −(Π2P,A ∪ σ2 P,A) ≠ ∅, with the corollary that also D ≠PA − (Π 2P, a ∪σ2 p, A) ≦ ∅. Expand

On Some Natural Complete Operators

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1985

This work investigates several natural operators which share similar properties and uses the concept of completeness to give a precise classification of the complexity of these operators. Expand

CLASSES OF PREDICTABLY COMPUTABLE FUNCTIONS

- Mathematics
- 1963

0. Introduction. In this paper we study a sequence of classes of computable functions for which a prediction of the complexity of the calculation may be made in a comparatively simple fashion. The… Expand

BPP and the Polynomial Hierarchy

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1983

It is shown by pure counting arguments that BPP is contained in ΣP2, the second level of the hierarchy of the polynomial hierarchy of Meyer and Stockmeyer. Expand

The Polynomial-Time Hierarchy

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1976

The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established. Expand

The Complexity of Enumeration and Reliability Problems

- Mathematics, Computer Science
- SIAM J. Comput.
- 1979

For a large number of natural counting problems for which there was no previous indication of intractability, that they belong to the class of computationally eqivalent counting problems that are at least as difficult as the NP-complete problems. Expand

The Complexity of Computing the Permanent

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1979

Abstract It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations. Related… Expand

Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)

- Mathematics, Computer Science
- FOCS
- 1985

We present exponential lower bounds on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the… Expand

The complexity of approximate counting

- Computer Science
- STOC
- 1983

The complexity of computing approximate solutions to problems in #P is classified in terms of the polynomial-time hierarchy (for short, P-hierarchy) in order to study a class of restricted, but very natural, probabilistic sampling methods motivated by the particular counting problems. Expand