patternMinor
Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$
Viewed 0 times
mathrmloghierarchytimebigcup_classescomplexity
Problem
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.
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.
Solution
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).
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).
Context
StackExchange Computer Science Q#33824, answer score: 3
Revisions (0)
No revisions yet.