※ 引述《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来做判断？
谢谢！