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),所以這個解答不太能接受。
大神是否有其他看法?