演算法›Ch5 NP Complete Problems第 3 題/共 30 題
3. NP-Complete、計算複雜度理論
#AL-05-003中NP-Complete計算複雜度理論
How many of the statements below are known to be true?
- Every problem in NP is polynomial-time reducible to some NP-hard problem.
- Every problem in NP is polynomial-time reducible to some NP-complete problem.
- Every problem in NP is polynomial-time reducible to some problem solvable within polynomial time.
- Every problem in NP is polynomial-time reducible to some problem solvable within exponential time.
參考答案與解析
答案 (D) 3。逐一檢查四句:①NP 問題都可歸約到某個 NP-hard 問題——true(NP-hard 定義本身)。②都可歸約到某個 NP-complete 問題——true(SAT 等 NP-complete 問題存在,且 NP-complete⊆NP-hard)。③都可歸約到某個多項式時間可解問題——這若對所有 NP 問題(含 NP-complete)成立,會直接推出 P=NP,這並非已知為真,false。④都可歸約到某個可在指數時間內解決的問題——true(NP⊆EXPTIME,問題本身用 brute force 就在指數時間可解,可視為归约到自己)。故真命題共 3 句。
📄 台大115
▤完整推導請見《WH 資工筆記 · 演算法》Ch5 NP Complete Problems