作者NTUmaki (西木野真姬)
看板Grad-ProbAsk
标题[理工] 演算法 NP-complete
时间Mon Aug 31 19:16:32 2020
定理 6-1
若存在一个NP-complete 问题 为 polynomial-time solvable 则 P=NP
老师上课的说法是 NP里面最难的问题可以多项式时间内解决，所以NP 包含於 P ，然後P本来就包含於NP，得证。
我的详细证明想法是这样，不知道对不对
存在一个NP-complete为 P
NP-complete为属於NP且为NP-hard
NP-hard 是 所有NP 都可以被polynomially reduce 到它
所以如果他是polynomials-time solvable 则所有NP问题都可以polynomially reduce 成它 再 polynomials solve it 因此所有NP包含於P
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.8.161.10 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1598872594.A.174.html
1F：推 mi981027: 是的 08/31 19:18
3F：→ NTUmaki: /PTDJh9s.jpg 08/31 19:22
5F：→ NTUmaki: 铅笔圈起来的地方，应该是想说所有NP都可以reduce到A 所 08/31 19:23
6F：→ NTUmaki: 以也可以reduce到 B 因此得证B是NP-hard? 08/31 19:23
7F：→ NTUmaki: 根据NP-hard定义看的话应该是多打complete 还是我哪边搞 08/31 19:24
8F：→ NTUmaki: 错 08/31 19:24
9F：→ mi981027: 嗯嗯对 这边应该是对於所有C属於NP 他多打了 09/01 10:04
10F：→ mi981027: 不过依照定义来看 他这样打也不算出错 09/01 10:04