[理工] 105清大（P&NP)!

看板Grad-ProbAsk作者 (andrew)時間4年前 (2020/01/21 20:33), 編輯推噓2(2推 0噓 18→)
留言20則, 6人參與, 4年前最新討論串1/2 (看更多)
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1579609985.A.10F.html
→
01/21 20:35, 4年前 , 1F
B NPC也算是NP hard啊
01/21 20:35, 1F
→
01/21 20:37, 4年前 , 2F
對，但題目說npc應該是希望找出同時屬於np,np hard的集
01/21 20:37, 2F
→
01/21 20:37, 4年前 , 3F
合，可是沒有先令x屬於np，有可能x是屬於np hard但不屬
01/21 20:37, 3F
→
01/21 20:37, 4年前 , 4F
於np
01/21 20:37, 4F
→
01/21 20:45, 4年前 , 5F
B 妳想法沒錯 c我的解釋是可能要階乘甚至指數指數
01/21 20:45, 5F
推
01/21 20:56, 4年前 , 6F
(c)會不會是說 某些特殊情況可以在p內解 像是bipartit
01/21 20:56, 6F
→
01/21 20:56, 4年前 , 7F
e找ham path之類的
01/21 20:56, 7F
→
01/21 21:00, 4年前 , 8F
這我有點不確定，但若存在npc可在p解，似乎直接等價於p=
01/21 21:00, 8F
→
01/21 21:00, 4年前 , 9F
np，因為所有np都可reduce到它
01/21 21:00, 9F
→
01/21 21:10, 4年前 , 10F
decision不等於在p啊
01/21 21:10, 10F
→
01/21 21:14, 4年前 , 11F
一個叫optimization problem一個叫decision problem
01/21 21:14, 11F
→
01/21 21:19, 4年前 , 12F
好像回答的文不對題 前面就先別看 我誤會了 簡單來說要找Ham
01/21 21:19, 12F
→
01/21 21:19, 4年前 , 13F
iltonian cycle是NPC 但如果今天前提是輸入的圖一定是cycle
01/21 21:19, 13F
→
01/21 21:19, 4年前 , 14F
當然是可解 他問題在於 for all kind這件事 如果我沒理解錯
01/21 21:19, 14F
→
01/21 21:19, 4年前 , 15F
那存在一種種類的輸入可以簡單的解出來的話這敘述就不成立
01/21 21:19, 15F
→
01/21 21:24, 4年前 , 16F
我認為for all kind of inputs拿掉就沒問題
01/21 21:24, 16F
推
01/21 22:14, 4年前 , 17F
錯在他已經假設了P不等於NP吧 但這是還沒有被證明
01/21 22:14, 17F
→
01/21 22:14, 4年前 , 18F
的問題
01/21 22:14, 18F
→
01/21 23:16, 4年前 , 19F
3.用SAT想 考慮clause為單獨一個X1 判斷他可否滿足只
01/21 23:16, 19F
→
01/21 23:16, 4年前 , 20F
需O(1) 因此input很小的時候不一定需要指數時間
01/21 23:16, 20F
‣ 更多 Aa841018 的文章
文章代碼(AID): #1U9k-14F (Grad-ProbAsk)
‣ 更多 Aa841018 的文章
文章代碼(AID): #1U9k-14F (Grad-ProbAsk)