[理工] 演算法NP-Complete T or F

看板Grad-ProbAsk作者 (我覺得我還不錯啊)時間7年前 (2018/10/19 09:36), 編輯推噓0(0推 0噓 2→)
留言2則, 2人參與, 7年前最新討論串1/1
http://i.imgur.com/QUlm1W2.jpg
不好意思想請問一下11題的(3)是錯在哪邊？ 題目右下角是我嘗試照著題意畫的轉換圖 感覺起來是B之instance花O(nlgn)轉換到A問題，然後花O(T(n))解A的instance，就等價於B之decision 所以看起來應該是B<=(A比較難) 所以錯的地方應該是lower bound of A=Ω(n2 ) 這段改成upper bound of A=O(n2 )是不是就對了？ ----- Sent from JPTT on my Asus ASUS_Z016D. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.233.13.180 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1539913005.A.411.html
→
10/19 10:30, 7年前 , 1F
lower bound 要在簡單的問題上
10/19 10:30, 1F
→
10/19 10:37, 7年前 , 2F
所以lower bound是要在B上嗎？
10/19 10:37, 2F
‣ 更多 wilson50101 的文章
文章代碼(AID): #1RoJKjGH (Grad-ProbAsk)