1
$\begingroup$

Question 1: Is it known that $\mathrm{QP}=\cup_{k}\mathrm{TIME}(2^{\mathrm{log}^k(n)})$ has any complete problem?

Question 2: Can this be used to simplify the computational complexity theory at all?

$\endgroup$
2
$\begingroup$

Question 1: NO

Question 2: NO

Question 1: Assume to the contrary that $\mathrm{QP}$ has a complete problem $\mathrm{L}\in\mathrm{QP}$.

Then, there exists $k$ such that $\mathrm{L}\in\mathrm{TIME}(2^{\mathrm{log}^k(n)})$. Consider an arbitrary problem $\mathrm{L}'\in\mathrm{QP}$, by completeness of $\mathrm{L}$, we have that $\mathrm{L}'\leq_p\mathrm{L}$, i.e there exists a many-one polynomial-time reduction $f$ from $\mathrm{L}$ to $\mathrm{L}'$. So, given any instance $x\in\Sigma^*$ with $|x|=n$, we first reduce $x$ to $f(x)$. Since $f$ is polynomial-time computable, we have that $|f(x)|=n^{O(1)}$. Now, we run the $2^{\mathrm{log}^k(n)}$ time-bounded TM deciding $\mathrm{L}$, and accept or refute accordingly.

We now estimate the time complexity of this TM for $\mathrm{L}'$. We have: $$2^{\mathrm{log}^k(n^{O(1)})}=2^{O(1).\mathrm{log}^k(n)}=2^{O(\mathrm{log}^k(n))}$$

So, the whole class $\mathrm{QP}$ collapse to $\mathrm{TIME}(2^{O(\mathrm{log}^k(n))})$ violating the Time Hierachy Theorem.

Thus, $\mathrm{QP}$ does not have any complete problem.

Question 2: The unconditional lack of complete problem of $\mathrm{QP}$ unconditionally separates it from $\mathrm{NP}$, $\mathrm{co}$-$\mathrm{NP}$, $\mathrm{PP}$, $\oplus P$, $\mathrm{US}$, $\mathrm{PSPACE}$. But that is of no help for computational complexity theory, since the interesting nasty, stubborn classes such as $\mathrm{ZPP}$, $\mathrm{RP}$, $\mathrm{co}$-$\mathrm{RP}$, $\mathrm{BPP}$, $\mathrm{MA}$, $\mathrm{AM}$ all remain elusive to whether any of them has a complete problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy