为什么多个字符串的最长公共子序列是 NP-Hard？
Why is the longest common subsequence for multiple strings NP-Hard?
我很难理解为什么多个字符串 (k > 2) 的最长公共子序列问题是 NP-Hard。我知道两个长度为 l1, l2 的字符串的 LCS 问题可以在 O(l1*l2) 时间内解决。我的问题是为什么我们不能一次找到两个字符串的LCS，例如：
LCS(abcd, ad, abc) = LCS(LCS(abcd, ad), abc) = LCS(ad, abc) = a
对于 k 个字符串，此算法的复杂度为 O(k*Max_length^2)。为什么这是错误的？
LCS(x, y, z) = LCS(x, LCS(y, z)) 通常不正确。例如：
LCS(bb, aaabb, bbaaa) = bb
LCS(bb, LCS(aaabb, bbaaa)) = LCS(bb, aaa) ≠ bb
我很难理解为什么多个字符串 (k > 2) 的最长公共子序列问题是 NP-Hard。我知道两个长度为 l1, l2 的字符串的 LCS 问题可以在 O(l1*l2) 时间内解决。我的问题是为什么我们不能一次找到两个字符串的LCS，例如：
LCS(abcd, ad, abc) = LCS(LCS(abcd, ad), abc) = LCS(ad, abc) = a
对于 k 个字符串，此算法的复杂度为 O(k*Max_length^2)。为什么这是错误的？
LCS(x, y, z) = LCS(x, LCS(y, z)) 通常不正确。例如：
LCS(bb, aaabb, bbaaa) = bb
LCS(bb, LCS(aaabb, bbaaa)) = LCS(bb, aaa) ≠ bb