改了一半考卷
发现很多同学观念完全错误 如以下的例子:
我们想要证 问题A(independent set) 是 NPC
所以我们找一个已经是 NPC 的 问题B(clique)
但大家陷在一直想要解 问题A(independent set) 的迷思里面
所以发现 问题A(independent set) 可以用 问题B(clique) 来解的时候
就很高兴地说 问题A(independent set) 是 NPC(NP-hard)
这是完完全全错误的!!!!!!!! (方向错误)
既然你都知道 问题B(clique) 是 NPC 了
那你还用它来解 问题A(independent set) 做什么?
我们又不知道有没有一个更简单的 问题C 也可以来解 问题A(independent set)
搞不好 问题C 是 P，那么 问题A(independent set) 也就是 P 了啊
所以上面的做法只是拿一个很难的 问题B 来解 问题A
然后就说 问题A 也好难.....
这样当然是错误的
所以请大家记好 我们现在不是要说明如何解这个问题
而是要说明这是个 NPC 问题
just murmuring