# On different characterizations of $\mathsf P$

In here it was clarified that $\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})\subsetneq\cap_{\epsilon>0}\mathcal C(n^{n^\epsilon})$ where $\mathcal C(t(n))$ is the class of problems solvable in $O(t(n))$ time.

My query now is whether there is a function of $g(n,\epsilon)$ that non-trivially depends on $\epsilon$ with $g(n,\epsilon)<g(n',\epsilon')\implies\epsilon<\epsilon'\vee n<n'$ such that $\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})=\cap_{\substack{\epsilon>0}}\mathcal C(n^{g(n,\epsilon)})$ can hold?

That is I seek a different characterization of $\mathsf{P}$.

• @D.W. $\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})=\mathsf P$? no? – Turbo Dec 15 '16 at 9:36
• @D.W. Suppose that for every $k$ there exist infinitely many $n$ such that $g(n) > n^k$. Construct an increasing sequence $n_k$ such that $g(n_k) > n_k^k$. Define a monotone function $f$ so that $f(n_k) = k-1$. Then $f = \omega(1)$ but $g \neq O(n^{f(n)})$. – Yuval Filmus Dec 15 '16 at 19:01

I will consider the following simpler version of your question: is there a function $g(n,\epsilon)$ such that the following are equivalent, for a function $f(n)$:

1. $f$ is bounded.
2. For every $\epsilon > 0$ there exists $N$ such that for $n \geq N$, $f(n) \leq g(n,\epsilon)$.

Consider first the case in which $g(n,\epsilon_1)$ eventually exceeds $g(n,\epsilon_2)$ whenever $\epsilon_1 > \epsilon_2$ (like your example $g(n,\epsilon) = n^\epsilon$). Then the second condition can be rewritten equivalently as

1. For every integer $M$ there exists $N$ such that for $n \geq N$, $f(n) \leq g(n,1/M)$.

Define the function $$f(n) = \max_{M \leq n} g(n,1/M).$$

This function satisfies condition (3), and so is bounded, say $f \leq C$. This implies $g(n,1) \leq C$. But then the bounded function $C+1$ doesn't satisfy condition (3) for $M=1$. This contradiction shows that under the stated constraint, no function $g$ fits the bill.

On the other hand, as you mention, $f$ is bounded iff it is eventually dominated by every $\omega(1)$ integer function. Indeed, suppose that $f$ is unbounded. Then for every integer $M$ there exist infinitely many $n$ such that $f(n) \geq M$. In particular, we can find an increasing sequence $n_1,n_2,\ldots$ such that $f(n_M) \geq M$. Define a function $g$ by $g(n) = M-1$ for $n_{M-1} < n \leq n_M$. Then $g = \omega(1)$ but $f$ is not eventually dominated by $g$.

The functions from $\mathbb{N}$ to $\mathbb{N}$ have the cardinality of the continuum, and so they can be put (constructively!) in one-to-one correspondence with the real interval $(0,\infty)$. This immediately gives a function $g(n,\epsilon)$ which does fit your bill, though is not particularly natural.

• Sorry this is a bit abstract for me. So the verdict is there is no $g(n,\epsilon)$ (natural or non-natural) with my requirements such that $$\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})=\cap_{\substack{\epsilon>0}}\mathcal C(n^{g(n,\epsilon)})=\mathsf P$$ holds. Correct? – Turbo Dec 16 '16 at 2:33
• There does exist such a function (second half of answer), but it's probably not what you meant (first half of answer). – Yuval Filmus Dec 16 '16 at 6:16