# Prove that $coNP \neq NTIME(n^2)$

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?

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.
• 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? Jan 14, 2023 at 14:07
• 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$. Jan 14, 2023 at 14:11