作者:
FRAXIS (喔喔)
2014-10-19 20:08:19※ 引述《qoojordon (穎川琦)》之銘言：
: 這邊有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 <