7
$\begingroup$

The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem

For instance, the Arora-Barak book explains the theorem using $g(n) = n$ and $G(n) = n^{1.5}$ - but, I can see that $n \in o(n^{1.5})$ as well! So, I'm trying to better understand what "extra" time is guaranteed by specifying that in order for $\text{NTIME}(g(n))$ to be a proper subset of $\text{NTIME}(G(n))$, $g(n + 1) = o(G(n))$, not $g(n) = o(G(n))$...

$\endgroup$
12
$\begingroup$

One example is $g(n) = 2^{2^{n-1}}$, $G(n) =2^{2^{n}}$.

We have $g(n) = \sqrt{G(n)}$, so $g(n) = o(G(n))$.

Meanwhile, of course, $g(n+1) = G(n)$ so $g(n+1) = \Theta(G(n))$, so $g(n+1)\neq o(G(n))$

Why double exponential? When we add one to $n$, we want the effect to be more than a multiplicative constant (because big $O$ notation hides multiplicative, and therefore additive constants). Let's make it simple and say that we want adding 1 to $n$ to have a polynomial effect on the value of $g(n)$. When you add a constant to $n$:

  • a linear function is increased by an additive constant

  • an exponential function is increased by a multiplicative constant

  • a double exponential function is increased polynomially (by a power of two in our example, hence $g(n)^2 = G(n)$)

We can also have $g(n) = n^n$, $g(n) = n!$, etc., where $G(n) = g(n-1)$. In general we can let $g(n) = f(n)^n$, where $f(n) = \omega(1)$ and $f$ is nondecreasing. Then we have:

$$\lim_{n\to\infty} \frac{g(n)}{G(n)} = \lim_{n\to\infty} \frac{g(n)}{g(n+1)} = \lim_{n\to\infty}\frac{f(n)^n}{f(n+1)^{n+1}} \leq \lim_{n\to\infty}\frac{f(n)^n}{f(n)^{n+1}} = \lim_{n\to\infty}\frac{1}{f(n)} = 0$$

So we've shown $g(n) = o(G(n))$ using the limit definition (the last step is because $f(n) = \omega(1)$). Therefore, functions like $(\log\log n)^n$ and even $\alpha(n)^n$ where $\alpha$ is the inverse Ackermann function, will do the trick for us as well.

$\endgroup$
  • $\begingroup$ Does anyone know of a smaller or simpler $g$, $G$ which don't use this outline but fit the requests of the OP? $\endgroup$ – SamM Nov 26 '12 at 22:26
8
$\begingroup$

Take $g(n)= n!$ and $G(n) = (n+1)!$.

$\endgroup$

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.