1. We have the following definitions and theorem related to NP-completeness.
Definition 1. Let X1 and X2 be tow problems. X1 polynomially reduces to X2 (written as ) if and
only if X1can be solved in polynomial time, by using a polynomial time algorithm which solves X2.
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.)
【題組】 (B) (5%) By the above definitions and theorem, show the following statement is true or false. You should
also show your reasons. If the reasons are incorrect, then you get no point.
Statement: An NPC problem can polynomially reduce to any NPC problem.