[理工] 103中央離散必要但不充分

看板Grad-ProbAsk作者 (干我屁事喔北七)時間5年前 (2020/01/25 15:13), 5年前編輯推噓7(7推 0噓 18→)
留言25則, 5人參與, 5年前最新討論串1/1
https://imgur.com/o2C9aKo
單純想問題意 這題說要找關係為必要但不充分的敘述， 也就是說左到右成立但右到左不成立 或者是右到左成立但左到右不成立 對吧 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 117.19.236.163 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579936417.A.79A.html
→
01/25 15:22, 5年前 , 1F
不是或者，是只有右到左成立且左到右不成立
01/25 15:22, 1F
想問C選項是對還是錯 ※ 編輯: ponwar87123 (117.19.236.163 臺灣), 01/25/2020 15:44:33
→
01/25 16:02, 5年前 , 2F
錯吧 ，根本沒有關係吧 不必要也不充分
01/25 16:02, 2F
→
01/25 16:19, 5年前 , 3F
NP是可以多項式時間內驗證 就叫NP
01/25 16:19, 3F
推
01/25 18:53, 5年前 , 4F
C是對的吧 若problem屬於NP 則存在指數複雜度的演算法
01/25 18:53, 4F
→
01/25 18:54, 5年前 , 5F
z大說的應該是sufficient
01/25 18:54, 5F
推
01/25 18:57, 5年前 , 6F
講精確一點 任何在NP裡的problem一定存在O(2^p(n))的演算
01/25 18:57, 6F
→
01/25 18:57, 5年前 , 7F
法，其中p(n)是非決定性算法的步驟
01/25 18:57, 7F
→
01/25 18:58, 5年前 , 8F
01/25 18:58, 8F
→
01/25 18:58, 5年前 , 9F
可以參考
01/25 18:58, 9F
→
01/25 19:21, 5年前 , 10F
借題問個 NP-hard有exponential time algorithm 嗎
01/25 19:21, 10F
→
01/25 19:22, 5年前 , 11F
如果有的話 (C)就是必要但不充分了吧
01/25 19:22, 11F
推
01/25 21:47, 5年前 , 12F
MASA大說的我不是很懂 C選項不是討論NP嗎？
01/25 21:47, 12F
推
01/25 23:03, 5年前 , 13F
NP-hard不屬於NP
01/25 23:03, 13F
→
01/25 23:03, 5年前 , 14F
如果有一NP-hard但不是NPC的問題有exponential algorithm
01/25 23:03, 14F
→
01/25 23:03, 5年前 , 15F
這樣的話就不能靠exponential algorithm判斷是否屬於NP
01/25 23:03, 15F
→
01/25 23:03, 5年前 , 16F
只是我不知道這前提是否是對的XD 也有可能我觀念有錯
01/25 23:03, 16F
→
01/25 23:03, 5年前 , 17F
想問大家的想法
01/25 23:03, 17F
→
01/25 23:16, 5年前 , 18F
我覺得還是不必要 因為如果p=np 那就不用指數
01/25 23:16, 18F
推
01/25 23:27, 5年前 , 19F
若p則q 這跟有沒有必要指數沒什麼關係
01/25 23:27, 19F
→
01/25 23:27, 5年前 , 20F
*必要改成用不用
01/25 23:27, 20F
推
01/25 23:31, 5年前 , 21F
01/25 23:31, 21F
→
01/25 23:31, 5年前 , 22F
01/25 23:31, 22F
→
01/25 23:31, 5年前 , 23F
^^^立宇題庫
01/25 23:31, 23F
推
01/26 08:26, 5年前 , 24F
我的意思跟詳解差不多XD 只是我不知道要用tractable這詞
01/26 08:26, 24F
→
01/26 08:26, 5年前 , 25F
@z大 即使P=NP 所有NP還是存在exponential algorithm吧
01/26 08:26, 25F
‣ 更多 ponwar87123 的文章
文章代碼(AID): #1UA-gXUQ (Grad-ProbAsk)