作者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/cn.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