1
$\begingroup$

Intuitively it would seem like these equalities are false since DTIME(n) and DSPACE(N) are in terms of deterministic Turing machines and NP is non-deterministic, but I'm struggling to come up with a convicing argument as to why this is. I'm assuming that both the Time and Space Hierarchy Thoerems must be used but I'm just not quite sure how. I'm hoping someone can lead me in the right direction.

$\endgroup$
2
$\begingroup$

$DTIME(n^2) \subseteq \mathcal{P} \subseteq \mathcal{NP}$ and by the Time Hierarchy Theorem $DTIME(n^2) \nsubseteq DTIME(n)$ Therefore $\mathcal{NP} \neq DTIME(n)$

$\endgroup$

Your Answer

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

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