[理工] 103中央離散必要但不充分 ponwar87123 PTT批踢踢實業坊

作者: ponwar87123 (干我屁事喔北七) 2020-01-25 15:13:34

https://imgur.com/o2C9aKo
單純想問題意
這題說要找關係為必要但不充分的敘述，
也就是說左到右成立但右到左不成立
或者是右到左成立但左到右不成立
對吧

作者: Ricestone (麥飯石) 2020-01-25 15:22:00

不是或者，是只有右到左成立且左到右不成立

作者: a80242002 (寬寬) 2020-01-25 16:02:00

錯吧，根本沒有關係吧不必要也不充分

作者: zuchang (chang) 2020-01-25 16:19:00

NP是可以多項式時間內驗證就叫NP

作者: mistel (Mistel) 2020-01-25 18:53:00

C是對的吧若problem屬於NP 則存在指數複雜度的演算法z大說的應該是sufficient講精確一點任何在NP裡的problem一定存在O(2^p(n))的演算法，其中p(n)是非決定性算法的步驟https://wiki.c2.com/?NpComplete可以參考

作者: MASAGA (和泉千晶我老婆) 2020-01-25 19:21:00

借題問個 NP-hard有exponential time algorithm 嗎如果有的話 (C)就是必要但不充分了吧

作者: mistel (Mistel) 2020-01-25 21:47:00

MASA大說的我不是很懂 C選項不是討論NP嗎？

作者: MASAGA (和泉千晶我老婆) 2020-01-25 23:03:00

NP-hard不屬於NP如果有一NP-hard但不是NPC的問題有exponential algorithm這樣的話就不能靠exponential algorithm判斷是否屬於NP只是我不知道這前提是否是對的XD 也有可能我觀念有錯想問大家的想法

作者: zuchang (chang) 2020-01-25 23:16:00

我覺得還是不必要因為如果p=np 那就不用指數

作者: mistel (Mistel) 2020-01-25 23:27:00

若p則q 這跟有沒有必要指數沒什麼關係*必要改成用不用https://i.imgur.com/Me0QGpo.jpg https://i.imgur.com/bP2in9K.jpg^^^立宇題庫

作者: MASAGA (和泉千晶我老婆) 2020-01-26 08:26:00

我的意思跟詳解差不多XD 只是我不知道要用tractable這詞@z大即使P=NP 所有NP還是存在exponential algorithm吧

繼續閱讀