# How to prove existence of the language

Consider such question:

(Prove or disprove) There exists a language in $TIME(2^{n^2})$ that is not in $NTIME(n)$.

I guess that answer is yes because $TIME(2^{n^2})$ and $NTIME(n)$ are totally different classes ($TIME(2^{n})$ and $NTIME(n)$ are the same classes, i guess). How to prove it strictly? (Or my guess is incorrect?)

• Use $NTIME(n) \subseteq TIME(2^{O(n)})$ together with the deterministic time hierarchy theorem. – Yuval Filmus Jun 16 '18 at 18:04

• $$\mathsf{NTIME}(n) \subseteq \mathsf{TIME}(2^{O(n)})$$, by deterministic simulation of nondeterminism.
• $$\mathsf{TIME}(2^{O(n)}) \subsetneq \mathsf{TIME}(2^{n^2})$$, by the time hierarchy theorem.