Examly題庫立即開始練習
國中教甄|資訊科技資訊科技109 年第 85 題單選題

Assuming P NP, which one of the following is true ?

ANP-complete = NP
BNP-complete P=正確答案
CNP-hard = NP
DP = NP-complete
答案與詳解
B
正確答案
官方答案 B 應解為在假設 P ≠ NP 下,NP-complete 與 P 無交集;若任一 NP-complete 在 P,就會推出 P = NP。

為什麼答案是 B

選項意旨為 NP-complete 與 P 無交集,或 NP-complete 不在 P 中。若存在 NP-complete 語言屬於 P,則所有 NP 語言都可先歸約到該語言再以 P 演算法解決,因而 P = NP,與假設不符。

載入中…

資訊科技 相關題目

想練更多資訊科技考古題?

Examly 收錄 38 萬+ 道歷屆題目,每題都有像這樣的精選詳解。免費下載,立即開練。

黑皮