首頁
題庫
網(wǎng)課
在線???/a>
桌面端
登錄
搜標(biāo)題
搜題干
搜選項(xiàng)
0
/ 200字
搜索
問答題
【簡答題】如何證明一個問題是NPC的。已知TSP是NPC的,試證明Hamilton問題也是NPC的。
答案:
先證明它至少是一個NP問題,再證明其中一個已知的NPC問題能約化到它(由約化的傳遞性,則NPC問題定義的第二條也得以滿足...
點(diǎn)擊查看完整答案
在線練習(xí)
手機(jī)看題
你可能感興趣的試題
問答題
【簡答題】簡述SAT問題和COOK定理。
答案:
S.AT問題:給定一組布爾變量V和一組由V組成的字句集合C,判定是否存在一組滿足C中所有子句的真值賦值。(布爾表達(dá)式可滿...
點(diǎn)擊查看完整答案
手機(jī)看題
問答題
【簡答題】為什么說,只要兩個不同的編碼系統(tǒng)是多項(xiàng)式相關(guān)的,就不影響算法復(fù)雜性的多項(xiàng)式性。
答案:
某問題在e1編碼下的算法時間復(fù)雜性是多項(xiàng)式T(n)。在e2編碼下,算法不變,算法時間復(fù)雜性T(P(n)),也是一個多項(xiàng)式...
點(diǎn)擊查看完整答案
手機(jī)看題
微信掃碼免費(fèi)搜題