卷別

資料結構與演算法(A)

選擇

國立臺灣大學 2022 · 考試 · 第 12 題

(5 points) Which of the following statement has been proved to be true?

(A)
An NP problem of size $n$ must take more than $poly(n)$ time to solve.
(B)
Any NP problem is polynomial-reducible to any NP-complete problem.
(C)
Any NP-complete problem is polynomial-reducible to any NP problem.
(D)
If an NP-complete problem can be solved by an approximation algorithm with ratio 2, any other NP-complete problem can also be solved by an approximation algorithm with a constant ratio.
(E)
none of the other choices

標準解析

AI 生成