3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What part of the notation don't you understand? $\endgroup$ – David Richerby Dec 4 '14 at 8:34
  • $\begingroup$ I added more to the question $\endgroup$ – Tingshuo Dec 4 '14 at 17:43
  • $\begingroup$ $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. $\endgroup$ – David Richerby Dec 4 '14 at 17:51
  • $\begingroup$ 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}$ $\endgroup$ – Tingshuo Dec 4 '14 at 18:27
  • 2
    $\begingroup$ No, in both cases, we're taking the union over all possible $c$. $\endgroup$ – David Richerby Dec 4 '14 at 19:13
3
$\begingroup$

Hint: Use the time hierarchy theorem.

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

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