algorithm - 如何证明最短公共超弦是 NP-Hard

Question

经过一些研究和许多 youtube 视频，我了解到证明问题是NP-Hard；您需要将该问题简化为已知的 NP-Hard 问题，例如子集和问题、停止问题、可满足性问题或旅行商问题。现在我的问题是最短公共超弦

• 输入：二进制字符串（0 和 1 的序列）的有限集 R = {r1, r2, ..., rm}；正整数 k。
• 问题：是否存在一个长度最多为 k 的二进制字符串 w，使得 R 中的每个字符串都是 w 的子字符串，即对于 R 中的每个 r，w 可以分解为 w = w0rw1 其中 w0，w1 是（可能为空的）二进制字符串？

在此链接中，它指出问题是 NP-Hard（https://www.geeksforgeeks.org/shortest-superstring-problem/），此外我正在使用那里所述的贪心算法来解决问题。

因此，我需要帮助选择要减少的 NP-Hard 算法以及减少它的方法。我不期望一个完整的解决方案（即使它会受到欢迎），只是指导就足够了。

标签： algorithmdiscrete-mathematicsproofdeterministicnon-deterministic