1
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ @D.W. $\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})=\mathsf P$? no? $\endgroup$ – Turbo Dec 15 '16 at 9:36
  • 1
    $\begingroup$ @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)})$. $\endgroup$ – Yuval Filmus Dec 15 '16 at 19:01
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Turbo Dec 16 '16 at 2:33
  • $\begingroup$ There does exist such a function (second half of answer), but it's probably not what you meant (first half of answer). $\endgroup$ – Yuval Filmus Dec 16 '16 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.