1
$\begingroup$

If we can solve the Hamiltonian path in time $O(n^4)$ then you can solve any other NPC problem in $O(n^4)$ time. Is it true of false? I think it is false, even tho Hamiltonian path problem in NPC it doesnt mean that all NPC problems will be solved in the same time.

$\endgroup$
2
$\begingroup$

You are correct. There might be an $NP$-complete problem that can only be translated into Hamiltonian path problem in $\Omega(n^{10})$ time, for instance. In which case an $\Omega(n^{10})$ translation and an $O(n^4)$ solution gives a total time of $\Omega(n^{10})$. The only thing you can be certain of is that the final time is bounded by a polynomial.

$\endgroup$
  • 1
    $\begingroup$ Small nitpick: the use of $O(\cdot)$ vs. $\Omega(\cdot)$. I guess you meant the reduction takes $\Omega(n^{10})$ time? $\endgroup$ – Clement C. Apr 28 '16 at 14:06
  • $\begingroup$ @ClementC. Yes, of course. $\endgroup$ – Arthur Apr 28 '16 at 14:33
  • $\begingroup$ @Arthur can you please edit your answer, I get confused now where are you talking about the reduction takes Ω(n^10) time? :( $\endgroup$ – Anastasia Netz Apr 28 '16 at 15:09
  • $\begingroup$ @ClementC. I get confused now where are you talking about the reduction takes Ω(n^10) time? :( $\endgroup$ – Anastasia Netz Apr 28 '16 at 15:12
  • $\begingroup$ Well, it is conceivable that any reduction from say 3SAT to Hamiltonian path "could have to take roughly $n^{10}$ time," which means that the reduction is $\Omega(n^{10})$. It is $\Omega$ and not $O$ since it'd be a lower bound on the time complexity of the reduction, not an upper bound. $\endgroup$ – Clement C. Apr 28 '16 at 15:18

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.