这边有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 <