# prove that Integer partition problem is NP complete using Hamiltonian Cycle

Show that Integer parition problem is NP-complete using the fact that Hamiltonian cycle is NP-Complete

My Thoughts :
Integer paritition problem is about partitioning a given set of integers into two sets with equal
sums. If I could show that Integer partition is polynomially reducible to Hamiltonian cycle
that would prove the given statement. I am not really sure how an instance of solution to IP
could lead to a hamiltonian cycle

• Showing that Integer Partition is polynomially reducible to Hamiltonian cycle would provide no information on whether Integer Partition is NP-hard. – Steven Apr 6 at 8:16
• But Given the fact that Hamiltonian cycle is NP-complete. If I reduce Integer parition to HC won't it prove that Integer partition is also NP-complete ? Or if not. What you suggest how to approach the given problem ? – Amit wadhwa Apr 6 at 9:01
• No, it won't. You need to reduce HC to Integer Partition. – Steven Apr 6 at 9:30
• okay got it. Any ideas how to approach that ? – Amit wadhwa Apr 6 at 9:40
• Show that (the decision version of) Hamiltonian Path (HP) is in NP. Invoke the Cook-Levin theorem to establish the existence of a polynomial-time reduction $f$ from HP to the Boolean Satisfiability (SAT) problem. Use any well-known polynomial-time reduction $g$ from SAT to 3SAT (i.e., the restriction of SAT to boolean formulas that are conjunctions of clauses each consisting of a disjunction of 3 literals). Finally, reduce 3SAT to Integer Parition (IP) via any chain of reductions found in textbooks. Let $h$ be the combined reduction. Then $h \circ g \circ f$ is a reduction from HP to IP. – Steven Apr 6 at 10:11