作者Aa841018 (andrew)
看板Grad-ProbAsk
标题[理工] 演算法257！（NP)
时间Sun Sep 1 15:11:46 2019
https://i.imgur.com/tu5Vo8A.jpg
请问2.（2） （106交大）
题目：A是NP则必定存在一个NP algo B可解A
这题为什麽是T啊？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.13.99.77 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1567321908.A.992.html
1F：→ JKLee: 因为NPC的存在 09/01 16:28
2F：推 mistel: 楼上说的是指所有NP都可以归约到NPC的意思吗？ 09/01 18:07
3F：→ Aa841018: 可是题目没特别说NPC存在…… 09/01 18:15
4F：推 mistel: NPC一定存在...图同构问题，Hamilton，3SAT都是啊 09/01 18:47
5F：→ Aa841018: 可是虽然所有np都可reduce到npc，但没人保证npc一定可以 09/02 18:05
6F：→ Aa841018: 被解决啊！ 09/02 18:05
7F：推 mistel: NPC蒐集的不是不能被解决的问题，而是认为没有多项式时间 09/02 18:24
8F：→ mistel: 解法的问题，因为一定都有暴力解存在，而且NPC其实是NP跟 09/02 18:24
9F：→ mistel: NP-Hard的交集 09/02 18:24
10F：→ firejox: NP的N是nondeterministic阿 不是Non-P 09/06 23:13
11F：→ firejox: NP problem can be solved by nondeterministic Turing 09/06 23:16
12F：→ firejox: machine in polynomial time. 09/06 23:17
13F：→ Aa841018: 哦！谢谢两位解惑！ 09/06 23:29