這邊有3個演算法的觀念想請教各位板友
Q1: NP-C的證明方式 與 reduce的概念
在探討一個問題 B 是不是NP-C的時候 , 都會用reduce的手法去說明 B 比較難
以我目前的理解 , 把問題A reduce 到問題 B , 代表 B 比 A 難
我的理由: 如果要知道B是否有解,可以用符合問題A的instance,經過多項式時間內
的f轉換,得到問題B的解
以證明Longest Path是NP-C為例 :
已知難度為NP-C的 問題A : G是否有Hamilton path ?
欲證明難度為NP-C的問題B : G是否存在一simple path長度≧k
要證明問題B為NP-C須說明兩件事情
(1) 問題B 是 NP
(2) 問題B 是 NP-C (用已知的NP-C問題reduce到問題B)
我的問題 : 證明(2)是否只要說明 A→B 即可 ?
書本上看到的寫法都會證明兩邊 A <