[section] [section]

[section] [section] [section]

In the motivational model, the estimator was restricted to lie in a class of functions that factor through a fixed mapping. Of course we are interested in more realistic notions of efficiency. In the present work consider restrictions on time complexity, access to random bits and size of advice strings. Spatial complexity is also of interest but treating it is out of our current scope. It is possible to consider weaker or stronger restrictions which we represent using the following abstraction:

Fix \(n\). A growth space \(\Gamma\) of rank \(n\) is a set of functions \(\gamma: {\mathbb{N}}^n \rightarrow {\mathbb{N}}\) s.t.

1. If \(\gamma_1, \gamma_2 \in \Gamma\) then \(\gamma_1 + \gamma_2 \in \Gamma\).

2. If \(\gamma_1 \in \Gamma\), \(\gamma_2: {\mathbb{N}}^n \rightarrow {\mathbb{N}}\) and \(\forall K \in {\mathbb{N}}^n: \gamma_2(K) \leq \gamma_1(K)\) then \(\gamma_2 \in \Gamma\).

We think of \(n\) as the number of parameters on which the resource restriction depends and \(m\) as the number of different resource types.