# How to prove Shortest Common Superstring is NP-Hard

After some research and many youtube videos I have learnt that to prove a problem is NP-Hard; you would need to reduce that problem to known NP-Hard problems such as Subset Sum Problem, Halting Problem, Satisfiability Problem or Traveling Salesman Problem. Now my problem is Shortest Common Superstring

• Input: A finite set R = {r1, r2, ..., rm} of binary strings (sequences of 0 and 1); positive integer k.
• Question: Is there a binary string w of length at most k such that every string in R is a substring of w, i.e. for each r in R, w can be decomposed as w = w0rw1 where w0, w1 are (possibly empty) binary strings?

In this link it states that the problem is NP-Hard(https://www.geeksforgeeks.org/shortest-superstring-problem/), besides I am using the greedy algorithm stated there to solve the problem.

So I need help with choosing which NP-Hard Algorithm to reduce to and a way to reduce it. I do not expect a full solution(even though it would be welcome), just guidance would be enough. I honestly do not have much clue on how to go about it.

• The reduction actually goes in the other direction: You pick a problem that you already know to be NP-hard, and reduce it to the problem you want to prove NP-hard. This is a common mistake. – j_random_hacker Dec 15 '19 at 2:31
• (This is a common mistake - getting the reduction direction wrong, that is.) – greybeard Dec 15 '19 at 3:39

Theorem 1 states that Hamilton path problem can be reduced to SCS even if all strings have fixed length $$H \ge 3$$.