※ 引述《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 <