作者Aa841018 (andrew)
看板Grad-ProbAsk
標題[理工] 105清大（P&NP)!
時間Tue Jan 21 20:33:03 2020
https://i.imgur.com/oiFkCVm.jpg
https://i.imgur.com/G23Xg6H.jpg
想問（b)(c)
(b):這題詳解是不是少了假設x=np?因為沒有這假設，就算sat(npc) reduce to X，x也不
見得是npc說不定是np hard
(c):這和筆記好像有點矛盾，NPC不應該存在P的解法，否則NP=P
但NPC的某些input 又可以在非exponential time解開
時間複雜度排序：exponential>polynomial
（=n^k)
那如果不在exponential 解開，那肯定在polynomial範圍內，這豈不是和筆記內容矛盾?
不知道哪裡出錯…
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.8.74.23 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1579609985.A.10F.html
1F：→ zuchang: B NPC也算是NP hard啊 01/21 20:35
2F：→ Aa841018: 對，但題目說npc應該是希望找出同時屬於np,np hard的集 01/21 20:37
3F：→ Aa841018: 合，可是沒有先令x屬於np，有可能x是屬於np hard但不屬 01/21 20:37
4F：→ Aa841018: 於np 01/21 20:37
5F：→ zuchang: B 妳想法沒錯 c我的解釋是可能要階乘甚至指數指數 01/21 20:45
6F：推 misaka0120: (c)會不會是說 某些特殊情況可以在p內解 像是bipartit 01/21 20:56
7F：→ misaka0120: e找ham path之類的 01/21 20:56
8F：→ Aa841018: 這我有點不確定，但若存在npc可在p解，似乎直接等價於p= 01/21 21:00
9F：→ Aa841018: np，因為所有np都可reduce到它 01/21 21:00
10F：→ DLHZ: decision不等於在p啊 01/21 21:10
11F：→ DLHZ: 一個叫optimization problem一個叫decision problem 01/21 21:14
12F：→ DLHZ: 好像回答的文不對題 前面就先別看 我誤會了 簡單來說要找Ham 01/21 21:19
13F：→ DLHZ: iltonian cycle是NPC 但如果今天前提是輸入的圖一定是cycle 01/21 21:19
14F：→ DLHZ: 當然是可解 他問題在於 for all kind這件事 如果我沒理解錯 01/21 21:19
15F：→ DLHZ: 那存在一種種類的輸入可以簡單的解出來的話這敘述就不成立 01/21 21:19
16F：→ DLHZ: 我認為for all kind of inputs拿掉就沒問題 01/21 21:24
17F：推 gash55025502: 錯在他已經假設了P不等於NP吧 但這是還沒有被證明 01/21 22:14
18F：→ gash55025502: 的問題 01/21 22:14
19F：→ orz860708: 3.用SAT想 考慮clause為單獨一個X1 判斷他可否滿足只 01/21 23:16
20F：→ orz860708: 需O(1) 因此input很小的時候不一定需要指數時間 01/21 23:16