卷別

資料結構及演算法

選擇

國立政治大學 2026 · 考試 · 第 6 題

(5%) For two decision problems A and B, A is said to be polynomial-time reducible to B, denoted $A \le_P B$ , if there exists a function $f$ that is computable in polynomial time, such that for every input $x$ :

$x \in A \iff f(x) \in B$

Consider two decision problems A and B. It is given that problem A is NP-Complete. Which of the following statements regarding the direction of reduction is true?

(A)
If there exists a reduction $A \le_P B$ , and B belongs to the class NP, then B must be NP-Complete.
(B)
If there exists a reduction $B \le_P A$ , and B belongs to the class NP, then B must be NP-Complete.
(C)
If there exists a reduction $A \le_P B$ , then B must be verifiable in polynomial time.
(D)
If there exists a reduction $B \le_P A$ , then B must be strictly harder than A.

標準解析

AI 已複查