推 Billgaspeed: 13.b. 我看我們補習班老師說 如果要求optimal solut 01/20 14:44
→ Billgaspeed: ion 基本上是NP； 但如果只是要求approximate soluti 01/20 14:48
→ Billgaspeed: on 則可用greedy 來求 即為P 01/20 14:48
http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/101/2001.pdf
想問最後兩題
13(b)
每個Si只有兩個元素
這個好像是edge cover 要怎麼設計polynomial time的演算法?
想到的好像都不一定是optimal solution
14.
題目意思是要說明
n-tuple optimization problem 可以polynomial time reduce 到prime number problem嗎?
實在不大知道這種題目怎麼寫
感謝~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.120.228.196
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1451230609.A.692.html