https://i.imgur.com/ZDnToHr.jpg
有点疑惑C3和C4,对于C3我的想法是不能保证reduction是在O(n^3)完成,所以借由problem
B的算法设计出解problem A的算法,有可能不是O(n^3)只能说problemA可以在多项式时
间解决,因此C3倾向有误
而C4觉得有点纳闷,根据市面上的解答写说“使用解B的算法去设计解A的算法这个前提
下,若解A的算法为O(n^3),则可以设计出解B的算法也在O(n^3)解决”,但C4题目的假
设是A存在一个O(n^3)的算法,这并不能表示一定存在一个由解B的算法去组成的解A的演
算法,是在O(n^3),所以这个解答不太能接受。
大神是否有其他看法?