作者frank4133 (HYF)
看板Grad-ProbAsk
标题Re: [理工] 106清大计科 7 8
时间Tue Jan 31 11:25:23 2023
※ 引述《bochengchen (LFII)》之铭言：
: 请问各位大大
: 1.
: 第七题的第四小题
: https://imgur.com/u9KXQTy.jpg
: 这个叙述应该是false，想请问各位大大该如何解释？
看到原文底下有提到if p!=np, 没有>=1的approximation algo
但是有点困惑洪捷不是还教2-approximation vertex problem & TSP吗?
想请问是不是我有搞错哪里？
: 2.
: 第八题
: https://imgur.com/BVt9zsS.jpg
: 不知道这两个小题该怎麽做比较好呢？
这题题目提到given.... 所以我以为是指已知图G跟k值问是否满足每点degree >= |S|-k
所以是为一decision problem非求optimal solution
但是爬文看大家的讨论都是在证NP-hard
所以想请问是怎麽判断题目是要求optimal solution呢？
还是说只能以通常这种题目都是要证NP-complete来做判断？
谢谢！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.160.64.61 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1675135525.A.BD7.html
1F：推 jasonking3c: 第一题我也想问 近似演算法的p(n)不是必>1吗？ 01/31 19:47
2F：推 zhlun0428: 2的是etsp不是tsp 有限制条件 02/02 09:58
3F：→ frank4133: 了解，感谢！ 02/09 19:33