1
$\begingroup$

Given DTIME($n^2$) contains NTIME($n^{100}$) show that P=NP.

I think it's supposed to be straightforward but I just can't see it.

Take $L$, a language in NP. $L$ has a Turing machine which runs in NTIME$(f(n))$. If $f(n)$ is $\Omega(n^{100})$ it's obvious, but what about $O(n^{100})$?

$\endgroup$
  • 2
    $\begingroup$ Welcome to CS.SE! Do you have things backwards in the last sentence? The case where $f(n) = O(n^{100})$ seems like the easy one. $\endgroup$ – D.W. Dec 21 '16 at 22:22
  • $\begingroup$ Very closely related question; duplicate? $\endgroup$ – Raphael Apr 21 '17 at 5:08
1
$\begingroup$

Hint: What is the time complexity of the fastest nondeterministic Turing machine that is a decider for $SAT$?

$\endgroup$
  • $\begingroup$ And it can be proved by padding even without a complete language involved. $\endgroup$ – Willard Zhan Dec 22 '16 at 8:27
  • $\begingroup$ It can also be proved by first showing 0=1. $\endgroup$ – Yonatan N Apr 19 at 1:12

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.