演算法›Ch5 NP Complete Problems
第 21 題/共 30 題
◀ AL 21/30
21. NP-Complete、Reduction
#AL-05-021易NP-CompleteReduction

[2%] Suppose a problem called "Robot-Path-Planning" is a known NP-Complete problem. To prove that a related new problem "3-SAT" is also NP-Complete, we must demonstrate that "3-SAT" is in NP, and we must construct a polynomial-time reduction from "3-SAT" to "Robot-Path-Planning".

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