改了一半考卷
發現很多同學觀念完全錯誤 如以下的例子:
我們想要證 問題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