- 搜標(biāo)題
- 搜題干
- 搜選項(xiàng)
問答題
【簡答題】如何證明一個問題是NPC的。已知TSP是NPC的，試證明Hamilton問題也是NPC的。
答案：
先證明它至少是一個NP問題，再證明其中一個已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足...
你可能感興趣的試題
問答題
【簡答題】為什么說，只要兩個不同的編碼系統(tǒng)是多項(xiàng)式相關(guān)的，就不影響算法復(fù)雜性的多項(xiàng)式性。
答案：
某問題在e1編碼下的算法時間復(fù)雜性是多項(xiàng)式T（n）。在e2編碼下，算法不變，算法時間復(fù)雜性T（P（n）），也是一個多項(xiàng)式...
