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