# Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$

This is a true/false question:

For each integer $k > 1$, define the complexity class $\sf QP_k := \bigcup_{c > 0} Time(2^{c \log^k n})$. Then for all integers $k > 1$, $\sf QP_k \subsetneq QP_{k+1}$.

I have to prove it is true, or I have to give a counter example as to why it is not true.

I am having a lot of difficulty understanding the notation and also how to approach this problem. My understanding is that $c$ is some constant and effectively doesn't matter.

Edit: I guess I am unclear about how c and k work, the c seems like it doesn't matter so its asking us if there is every a point where from k = 2 to k = infinity if there will ever be a situation in which $2^{c \log^k n}$ = $2^{c \log^{k+1} n}$ for all c and n.

Is this the right interpretation?

I cannot find a single counter example that would make this true for any k, so it must be true. I am not sure how I would go about proving this is true.

• What part of the notation don't you understand? Dec 4, 2014 at 8:34
• I added more to the question Dec 4, 2014 at 17:43
• $c$ certainly matters. $\mathrm{Time}(f(n))$ is the class of languages that can be decided in at most $f(n)$ steps for an input of length $n$: we're not talking about $\mathrm{Time}(O(f(n))$. If you allow only $2^{\log^k n}$ steps, you can't do as much as you could in $2^{2\log^k n}$ steps, or $2^{3\log^k n}$ steps. Dec 4, 2014 at 17:51
• I understand what you are saying, but in the In the context of this problem are we assuming that the c value is the same for both $QP_{k}$ and $QP_{k+1}$ Dec 4, 2014 at 18:27
• No, in both cases, we're taking the union over all possible $c$. Dec 4, 2014 at 19:13

The first step, naturally, is understanding the question, that is, the definitions involved. The class $\mathsf{QP}_k$ consists of all problems solvable in time $2^{O(\log^k n)}$. We could similarly define $\mathsf{P}_k$ to consist of all problems solvable in time $O(n^k)$, and $\mathsf{P}$ to be a union over all $\mathsf{P}_k$: $$\mathsf{P}_k = \bigcup_{c>0} \mathsf{Time}(cn^k), \quad \mathsf{P} = \bigcup_{k>0} \mathsf{P}_k = \bigcup_{c,k>0} \mathsf{Time}(cn^k).$$ The class $\mathsf{QP} = \bigcup_{k>0} \mathsf{QP}_k$ is known as quasi-polynomial time. The question asks you to show that the corresponding hierarchy $\mathsf{QP}_2 \subseteq \mathsf{QP}_3 \subseteq \cdots$ is strict, that is $\mathsf{QP}_2 \subsetneq \mathsf{QP}_3 \subsetneq \cdots$. The same happens with the hierarchy corresponding to $\mathsf{P}$, again using the time hierarchy theorem: $\mathsf{P}_1 \subsetneq \mathsf{P}_2 \subsetneq \cdots$.
Why can't the same approach be used to prove $\mathsf{P} \subsetneq \mathsf{NP}$? Because here we're comparing deterministic computation to non-deterministic computation with the same time bounds, and there is no counterpart of the time hierarchy theorem which helps us here. Moreover, the time hierarchy theorems, in both the deterministic and non-deterministic case, are proved using diagonalization, a technique which is known to be unable to separate $\mathsf{P}$ from $\mathsf{NP}$ (in its vanilla form).