If we were to discover a deterministic algorithm capable of deciding, in polynomial time, whether a given graph contains a Hamiltonian path, would that imply that the problem SUBSETSUM belongs to P?

In this scenario, the existence of a deterministic polynomial-time algorithm for the Hamiltonian Path problem could lead to a polynomial-time reduction, allowing us to solve SUBSETSUM efficiently. The reduction would involve transforming an instance of SUBSETSUM into an equivalent instance of the Hamiltonian Path problem, applying the assumed algorithm to find a solution, and then using this solution to provide an answer for SUBSETSUM. Do you agree with this analysis?

  • $\begingroup$ Seems correct since both problems are NP complete. Although subset sum is weakly NP complete $\endgroup$
    – user136782
    Dec 2, 2023 at 16:22
  • $\begingroup$ @user136782 Thanks for ur answer ! $\endgroup$
    – Drat
    Dec 2, 2023 at 17:17
  • $\begingroup$ en.wikipedia.org/wiki/NP-completeness $\endgroup$
    – D.W.
    Dec 2, 2023 at 20:40
  • $\begingroup$ Exactly correct. Note that some problems make this easier than others. For example “Hamiltonian Path” is trivial if you can solve “Travelling Salesman”; your problem would be more difficult. $\endgroup$
    – gnasher729
    Dec 2, 2023 at 21:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.