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

關於 NP 完備性(NP-completeness)的敘述,下列何者最正確?

A若某問題屬於 NP-complete,表示該問題屬於 NP,且所有 NP 問題皆可在多項式時間內歸約至該問題正確答案
B若某問題屬於 NP-complete,表示目前已知存在多項式時間演算法可求解該問題
C若某問題屬於 NP-complete,表示目前在計算機理論中,已嚴格證明該問題不存在多項式時間的解法
D若某問題屬於 NP-complete,表示該問題求解上被認為困難,因此其候選解也無法在多項式時間內被驗證
答案與詳解
A
正確答案
NP-complete 的嚴格定義為該問題屬於 NP 且具備 NP-hard 特性(所有 NP 問題皆可多項式時間歸約至該問題)。

為什麼答案是 A

NP-complete 的標準定義即為該問題屬於 NP,且所有 NP 問題皆可在多項式時間內歸約(reduce)至該問題(即滿足 NP-hard 條件)。

載入中…

資訊科技 相關題目

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

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

黑皮