演算法›Ch5 NP Complete Problems第 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