作者wilson50101 (我觉得我还不错啊)
看板Grad-ProbAsk
标题[理工] 演算法NP-Complete T or F
时间Fri Oct 19 09:36:43 2018
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1539913005.A.411.html
1F：→ FRAXIS: lower bound 要在简单的问题上 10/19 10:30
2F：→ wilson50101: 所以lower bound是要在B上吗？ 10/19 10:37