如何证明最短公共超序列问题是np hard？
最短公共超序列问题(Shortest common supersquence):给一些字符串 比如 abc ,bcd
,def
然后可以判断是否有长度为 x 的字符串是这些字符串的父串，换句话说是否有一个长
度为x 的字符串能包含着三个字符串，比如abcdef就能，如果x为6 我们就能找到长度
为6的字符串包含了abc, bcd, def

再给一个例子，如果有这些字符串 abc, bcd, efg， x还是为 6，是否有长度为6的字
符串能包含这3个字符串么？没有！最短的是abcdefg 也就是说这三个字符串的最短公
共超序列长度为7

我现在不需要求最短公共超序列，但是我想证明这个问题是NP hard的，我想用TSP旅行
商问题 或者汉密尔顿路的问题reduce到这个问题上来证明这个最短公共超序列也是
nphard的，因为如果我们能把任何一个nphard的问题reduce到最短公共超序列问题上来
，就能证明最短公共超序列问题也是nphard的了。换句话说，我不明白怎么能给一个旅
行商问题或者汉密尔顿路径的问题，根据这些问题建立出一个最短公共超序列问题，然
后如果最短公共超序列问题可以解决，TSP或者汉密尔顿路径问题就可以解决。

我想了很久也想不明白，没能把模型对上，有知道的么？非常感谢！
--


[解决办法]
http://topic.csdn.net/u/20100427/12/01e86ec2-36bf-4948-8077-d3b55a111771.html
[解决办法]
up!