求助...如何证明最小编辑距离是近似最优解，是NP-难问题？
请大家帮帮忙，真不知道怎么去证明这两个问题...
[解决办法]
这个问题的证明应该是和你的算法的实现相关的，但是这个很可能是你的核心部分，所以我也不方便问。
一般，证明一个问题是np-problem可以很简单，也可以很复杂。通常的做法是把这个问题归结为一个已知的np-problem。
最著名的np-problem莫过于3-SAT problem。很多np-problem 都是通过归结为3-SAT problem得到证明的。
我设想了一下你的算法的实现。有可能可以归结为以下np-problem之一：
1．Vertex cover
2．Integer linear programming
3．TSP
4．Longest path
如果这几个都不对，那你就看一下3-SAT problem是怎么证明的。然后把你的问题归结为3-SAT problem。
希望对你有帮助
