1
$\begingroup$

I found this task in an old exam and couldn't get my head around it:

We define the class of languages $\mathsf{QP}$ as follows: $$\mathsf{QP} = \bigcup_{k \in \mathbb N} \mathsf{DTIME}(2^{\log(n)^k})$$ Show that there is no $L \in \mathsf{QP}$ such that $K \leq_p L$ for all $K \in \mathsf{QP}$

Some details on notation:

  • $\mathsf{DTIME(f)}$ conatains all languages $L$ for which there exists a deterministic turing machine that accepts all $w \in L$ with max $f(|w|)$ steps.
  • $\leq_p$ is used to express polynomial reducability

My attempt

Suppose, there is an $L\in\mathsf{QP}$ such that $K \leq_p L$ for all $K \in \mathsf{QP}$. Then $L \in \mathsf{DTIME}(2^{\log n^k})$ holds true for some natural number $k$. It follows, that $L'\leq L$ will also hold true for $L' \in \mathsf{DTIME}(2^{\log n^{k'}})$ with $k < k'$. That leads to $L' \in \mathsf{DTIME}(2^{\log n^{k}})$. But this contradicts $\mathsf{DTIME}(2^{\log n^k})\subsetneq \mathsf{DTIME}(2^{\log n^{k'}})$ which has to hold true because of the time hierarchy theorem.

Question

If this is correct, the same thing should be possible to argue that there is no such thing as $\mathsf{NP}$-hardness?

$\endgroup$
5
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Feb 27, 2022 at 22:37
  • $\begingroup$ It fine in the maths forum, though that would be ok here too $\endgroup$
    – Algebruh
    Feb 27, 2022 at 22:41
  • $\begingroup$ I don't know what the maths forum is, but we set our own standards and norms and expectations here. If you're talking about Math.SE, that is a different site with their own standards (but take a look at math.meta.stackexchange.com/a/20583/14578, math.meta.stackexchange.com/questions/22360/…, math.meta.stackexchange.com/a/31864/14578 to discover that even on Math.SE it appears the issue is nuanced and there are mixed opinions). $\endgroup$
    – D.W.
    Feb 27, 2022 at 22:48
  • $\begingroup$ there is a tag with proof verification on math.se, but nvm...I don'T see whats the problem with those kind of questions since yes/no answers are possible almost anytime and should be supported with a good reasoning imo. But you are right and I won't ask that kind of question again. Thank you sir! $\endgroup$
    – Algebruh
    Feb 27, 2022 at 22:50
  • $\begingroup$ I've edited the question. Hope it fits the guidelines now? $\endgroup$
    – Algebruh
    Feb 27, 2022 at 23:32

1 Answer 1

1
$\begingroup$

Let's back to the definition of many-one reduction.

Suppose, $L_1 \le_p L_2$. Then, there is a function $r$ such that $L_1(x) = L_2(r(x))$. Moreover, $r$ is polynomial-time computable so there exists a number $l$ such that $|r(x)| \in O(|x|^l)$. Note that if $L_2 \in \mathrm{DTIME}(f(n))$, then $L_1 \in \mathrm{DTIME}(f(n^l))$.

Now, if a language $L \in \mathrm{DTIME}(n^{(\log n)^{k_0}})$ is $\mathrm{QP}$-complete, the existence of the reduction implies $$\tag{1}\bigcup_{k \ge 0} \mathrm{DTIME}(n^{(\log n)^k}) \subseteq \bigcup_{l \ge 0} \mathrm{DTIME}([n^{(\log n)^{k_0}}]^l)$$ However, because $$\tag{2}[n^{(\log n)^{k_0}}]^l \in O(n^{(\log n)^{k_0 + 1}})$$ if we set $k = k_0 + 2$ in the LSH of (1), we have $$\tag{3}\mathrm{DTIME}(n^{(\log_n)^{k_0+2}}) \subseteq \mathrm{DTIME}(n^{(\log_n)^{k_0+1}})$$ contradicting the time hierarchy theorem.

Why cannot the same argument be applied to other classes such as $\mathrm{NP}$? $\mathrm{DTIME}$ can be changed to $\mathrm{NTIME}$, but the issue is we don't have the relation (2). There is no $k$ such that $(n^{k_0})^l \in O(n^k)$ for all $l \ge 0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.