申論題 - 阿摩線上測驗

申論題資訊

試卷：110年 - 110 國立中央大學_碩士班招生考試_資工類：資料結構與演算法#105890
科目：研究所、轉學考(插大)◆資料結構與演算法
年份：110年
排序：0

題組內容

1. We have the following definitions and theorem related to NP-completeness.

Definition 1. Let X₁ and X₂ be tow problems. X₁ polynomially reduces to X₂ (written as

) if and only if X₁can be solved in polynomial time, by using a polynomial time algorithm which solves X₂.
Definition 2. A problem is said to be a P (resp, NP) problem if it can be solved in polynomial time by a deterministic (resp,, non-deterministio) algorithn.
Definition 3. NP (resp., P) is the set of all NP (resp., P) problems.
Definition 4. A problem X is an NP-complete (NPC) problem if

and every NP problem reduces to X.
Cook's Theorem. NP=P if and only if the satisfiability (SAT) problem is a P problem. (This implies that every NP problem polynomially reduces to SAT.)

申論題內容

(C) (5%) By the above definitions and theorem, show the following staten ement is true or false. You should also show your reasons. If the reasons are incorrect, then you get no point. Statement: If an NPC problem can be solved in polynomial time by a deterministic algorithm, then all NP problems can also be solved in polynomial time by a deterministic algorithm.