作者oao521 (一樣的午後時光)
看板Grad-ProbAsk
標題[理工] 102成大程設
時間Sun Feb 9 22:01:19 2020
想請問這一題
https://i.imgur.com/SbLsXdQ.jpg
這一題題目不太明白在敘述什麼?
還有圈起來的符號(下標)是指什麼意思呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.76.143 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1581256881.A.D3C.html
1F：推 ok8752665: 請看演算法 np那章 02/09 22:04
2F：→ oao521: 啊 當兵完 演算法都忘光了 而且我演算法也讀一點點而已 02/09 22:06
3F：→ oao521: 好 我再去研究一下演算法 謝謝大大 02/09 22:06
4F：→ oao521: 剛剛去翻了一下NP-complete那章 02/09 22:14
5F：→ oao521: 想請問看完那一章 就可以明白這一題的觀念嗎? 02/09 22:15
6F：→ oao521: np那一章在後半段 這題在資結第一章 所以我先略過嗎? 02/09 22:15
7F：推 gash55025502: 圈起來的那個符號可以想成想成P1的難度小於等於P2 02/09 22:18
8F：→ gash55025502: 又P2屬於p 因此P1也屬於p 02/09 22:18
請問一下~ 為什麼知道P2屬於p呢?
※ 編輯: oao521 (118.166.76.143 臺灣), 02/09/2020 22:22:54
9F：推 gash55025502: 因為對lglgn取lg得lglgn*lglglgn<lgn 因此lglgn屬02/09 22:28
10F：→ gash55025502: 於多項式等級02/09 22:28
明白了 原來是從定義得知 感謝指點
※ 編輯: oao521 (118.166.76.143 臺灣), 02/10/2020 00:20:07
11F：→ tyjason0509: 是 再加上一點時間複雜度的概念就會懂了02/09 23:31
OK 我在研究一下 有問題再問你們~~ 乾蝦
※ 編輯: oao521 (118.166.76.143 臺灣), 02/10/2020 00:21:05
12F：→ 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