Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
    
Does anyone know of a smaller or simpler $g$, $G$ which don't use this outline but fit the requests of the OP? –  SamM Nov 26 '12 at 22:26

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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