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.