algorithm - 字符串到字符串更正问题 np 完整性证明

Question

我有这个任务来证明这个问题：

有限字母 £，两个字符串 x,y € £* 和一个正整数 K。有没有办法通过一系列 K 或更少的单个符号删除或相邻符号交换操作从字符串 x 导出字符串 y？

是 np 完全的。我已经知道我必须从集合覆盖问题的决策版本进行转换，但我不知道如何做到这一点。任何帮助，将不胜感激。

Answer 1

它看起来像修改后的Levenshtein distance。问题可以用 DP 在二次时间内解决。

从最小集覆盖 (MSC) 到此字符串校正问题的转换描述如下：

Robert A. Wagner
On the complexity of the Extended String-to-String Correction Problem
1975, Proceedings of seventh annual ACM symposium on Theory of computing 

简而言之，MSC问题：

给定有限集 x_1, ..., x_n 和整数 L，是否存在 {1,...,n} 的子集 J 使得 |J| <= L，并且

union_{j in J} x_j = union all x_i ?

令 w = 联合所有 x_i，令 t = |w| 和 r = t^2，并选择不在 w 中的符号 Q、R、S。

取字符串：

A = Q^r R x_1 Q^r S^(r+1) ... Q^r R x_n Q^r S^(r+1)
B = R Q^r ... R Q^r w S^(r+1) ... S^(r+1)   <- each ... is n times
and
k = (l+1)r - 1 + 2t(r+1)(n-1) + n(n-1)(r+1)^2/2 + (r*n + |x_1 ... x_n| - t)*W_d
[W_d is delete operation weight, can be 1.]

结果表明，如果源 MSC 问题是，则字符串校正问题 (A,B,k) 是可满足的。

从字符串构造中可以清楚地看出证明并非微不足道:-) 但管理起来并不太复杂。

Answer 2

提到的 NP 硬度证明仅适用于任意大的字母。对于有限字母，问题是多项式时间，请参阅 https://dblp.org/rec/bibtex/journals/tcs/Meister15