演算法›Ch5 NP Complete Problems
第 7 題/共 30 題
◀ AL 7/30
7. NP-Complete、多項式歸約
#AL-05-007中NP-Complete多項式歸約

What can you infer from the facts that PROBLEM-A is NP-complete and PROBLEM-A linear-time reduces to PROBLEM-B? C1C_1: If there exists an O(N3)O(N^3) algorithm for PROBLEM-B, then P=NPP=NP. C2C_2: If there does not exist an O(N3)O(N^3) algorithm for PROBLEM-B, then P≠NPP\ne NP. C3C_3: If there exists an O(N3)O(N^3) algorithm for PROBLEM-B, then there exists an O(N3)O(N^3) algorithm for PROBLEM-A. C4C_4: If there exists an O(N3)O(N^3) algorithm for PROBLEM-A, then there exists an O(N3)O(N^3) algorithm for PROBLEM-B.

📄 台大110
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch5 NP Complete Problems
本章題號 · 1–20 / 30