串来串纠正问题的NP完全性证明

Question

我有这样的任务，证明这个问题：

有限字母£，两个字符串X，Y€ £*，和一个正整数K.是 有一种方法可以从字符串x中得到字符串y ，其方式为K 或更少操作单个符号 删除或相邻符号 交换？

是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 = union all x_i，let t = | w |并且r = t^2，并且选择符号Q，R，S不在w中。

取串：

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.] 

结果表明，字符串字符串修正的问题（A，B，k）是可满足的当且仅当源MSC的问题是。

从字符串构造中可以清楚地看到证明并不简单:-)但是它的管理并不复杂。