作者silenteve (沉默的EVE)
看板Grad-ProbAsk
标题[理工] 105交大资演
时间Fri Jan 4 23:44:42 2019
https://i.imgur.com/cMhXsG8.jpg
想问一下这题各个选项t or f 跟原因
答案好像是d
谢谢～
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.82.8.135
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1546616685.A.600.html
1F：→ sdfg014025xx: (A)NPC 是NPH和NP的交集 01/05 00:45
2F：推 eggy1018: (B)要先有一组certificates,并在polynomial time verify 01/05 01:23
3F：→ eggy1018: 才是NP 01/05 01:23
4F：推 eggy1018: (C)不太确定 我觉得是NP-complete 可以互相reduce 的条 01/05 01:25
5F：→ eggy1018: 件 01/05 01:25
6F：推 eggy1018: (E)反过来了，因为可以reduce到SAT表示SAT比较原问题难 01/05 01:27
7F：→ eggy1018: 解，此时仍没办法知道原问题多难，所以不能确定原问题NP 01/05 01:27
8F：→ eggy1018: -complete, 反过来才有办法说明～ 01/05 01:27
9F：→ eggy1018: 以上有错 还麻烦各位大大指正了 01/05 01:27
10F：推 FRAXIS: (C) NPH 可能比 NPC 难 所以不一定可以 reduce 01/05 03:09