問(wèn)答題

【簡(jiǎn)答題】簡(jiǎn)述SAT問(wèn)題和COOK定理。

答案: S.AT問(wèn)題:給定一組布爾變量V和一組由V組成的字句集合C,判定是否存在一組滿足C中所有子句的真值賦值。(布爾表達(dá)式可滿...
題目列表

你可能感興趣的試題

問(wèn)答題

【簡(jiǎn)答題】為什么說(shuō),只要兩個(gè)不同的編碼系統(tǒng)是多項(xiàng)式相關(guān)的,就不影響算法復(fù)雜性的多項(xiàng)式性。

答案: 某問(wèn)題在e1編碼下的算法時(shí)間復(fù)雜性是多項(xiàng)式T(n)。在e2編碼下,算法不變,算法時(shí)間復(fù)雜性T(P(n)),也是一個(gè)多項(xiàng)式...
問(wèn)答題

【簡(jiǎn)答題】什么是“可證難解性”問(wèn)題,試舉出兩個(gè)例子。

答案: “可證難解性”問(wèn)題是不可判定的難解問(wèn)題和可判定的難解問(wèn)題的總稱,比如貨郎擔(dān)問(wèn)題,子圖同構(gòu)問(wèn)題。
微信掃碼免費(fèi)搜題