<noscript id="2g2wy"><optgroup id="2g2wy"></optgroup></noscript>

問答題

【簡答題】NP的假定之下，可以分成哪4類（舉例）？

答案： NP-hard問題在P≠NP的假定之下，可以分成4類：
1、有FPTAS（e.g.Knapsack）

你可能感興趣的試題

【簡答題】證明|「log2n」|=O（n）。

答案：

【簡答題】什么是偽多項式時間的算法？如何用動態(tài)規(guī)劃法求解背包問題？

答案：定義：設實例I的輸入規(guī)模為n，實例中的最大數(shù)為max（I），若算法的時間復雜性以某個二元多項式p（n，max（I））為上...