0
$\begingroup$

I need to prove that

$coNP \neq NTIME(n^2)$ using time hierarchy theorem.

as we know $DTIME(n^4)\subseteq P\subseteq coNP$

from time hierarchy theorem we can derive that $DTIME(n^4) \not \subseteq DTIME(n^2)$

therefore $DTIME(n^2) \neq coNP$

Also

as we know $NTIME(n^4)\subseteq NP$

from time hierarchy theorem we can derive that $NTIME(n^4) \not \subseteq NTIME(n^2)$

therefore $NTIME(n^2) \neq NP$

But anyway, I could not derive $coNP \neq NTIME(n^2)$ from any combination. Can someone give me a clue?

$\endgroup$

1 Answer 1

0
$\begingroup$

You should use the fact that $\textsf{NTIME}(n^2)\subsetneq \textsf{NP}$.

If $\text{co}\mathsf{NP} = \textsf{NTIME}(n^2)$, then $\text{co}\mathsf{NP} \subsetneq \mathsf{NP}$ and you can reach a contradiction.

$\endgroup$
3
  • $\begingroup$ why is $coNP \subsetneq NP$ a contradiction?, I mean, isn't the relationship between coNP and NP one of the greatest questions in complexity theory? $\endgroup$
    – Vahan
    Jan 14, 2023 at 14:07
  • $\begingroup$ Please note that there is a difference between $\text{co}\mathsf{NP}\not \subseteq \mathsf{NP}$ and $\text{co}\mathsf{NP}\subsetneq \mathsf{NP}$. What would be problematic is a strict inclusion. Note that for $A$ a problem, $\text{coco}A = A$. $\endgroup$
    – Nathaniel
    Jan 14, 2023 at 14:11
  • $\begingroup$ I got it, thanks)) $\endgroup$
    – Vahan
    Jan 14, 2023 at 14:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.