卷別

資料結構與演算法

選擇

國立臺灣大學 2025 · 考試 · 第 17 題

(5 points) Let $A, B, C, D, E$ be decision problems. We denote a polynomial time reduction with the symbol " $\le_p$ ". Suppose that $A \le_p B$ , $B \le_p C$ , $C \le_p D$ , and $C \le_p E$ . We also assume $A \in P$ and $B \in NP$ . Select all correct statement(s) below.

(A)
If $A$ is NP-hard, then $B \in P$ .
(B)
If $B$ is NP-hard and $E \le_p B$ , then $C$ is NP-complete and $D$ is NP-hard.
(C)
If $C$ is NP-complete, then both $D$ and $E$ are NP-complete.
(D)
If $D \in NP$ , then $C \in NP$ .
(E)
If $E$ is NP-hard, then $C$ is NP-hard.

標準解析

AI 已複查