推 ok8752665: 請看演算法 np那章 02/09 22:04
→ oao521: 啊 當兵完 演算法都忘光了 而且我演算法也讀一點點而已 02/09 22:06
→ oao521: 好 我再去研究一下演算法 謝謝大大 02/09 22:06
→ oao521: 剛剛去翻了一下NP-complete那章 02/09 22:14
→ oao521: 想請問看完那一章 就可以明白這一題的觀念嗎? 02/09 22:15
→ oao521: np那一章在後半段 這題在資結第一章 所以我先略過嗎? 02/09 22:15
推 gash55025502: 圈起來的那個符號可以想成想成P1的難度小於等於P2 02/09 22:18
→ gash55025502: 又P2屬於p 因此P1也屬於p 02/09 22:18
請問一下~ 為什麼知道P2屬於p呢?
※ 編輯: oao521 (118.166.76.143 臺灣), 02/09/2020 22:22:54
推 gash55025502: 因為對lglgn取lg得lglgn*lglglgn<lgn 因此lglgn屬02/09 22:28
→ gash55025502: 於多項式等級02/09 22:28
明白了 原來是從定義得知 感謝指點
※ 編輯: oao521 (118.166.76.143 臺灣), 02/10/2020 00:20:07
→ tyjason0509: 是 再加上一點時間複雜度的概念就會懂了02/09 23:31
OK 我在研究一下 有問題再問你們~~ 乾蝦
※ 編輯: oao521 (118.166.76.143 臺灣), 02/10/2020 00:21:05
→ Kedge: p1可以使用polynomial time的演算法reduce到p202/10 10:32
https://i.imgur.com/5XWqwiq.jpg
請問是因為橘色畫線部分,所以p1可以使用polynomial time的演算法reduce到p2?
※ 編輯: oao521 (180.217.145.212 臺灣), 02/10/2020 10:48:32
※ 編輯: oao521 (180.217.145.212 臺灣), 02/10/2020 10:50:23