Reduction
- Algorithms course
- Expert
- Lesson 7/41
- 4 min
Reduce one problem to another.
Reduction
Reduction transforms one problem into another. If A reduces to B in polynomial time and B is solved, A is solved.
This technique is used to prove problems NP-complete. To show a new problem is NP-complete, a known NP-complete problem is reduced to it.
Solution verification
Verifying whether a subset's sum equals the target is O(n). This shows subset sum is in NP.
Verification is polynomial; so subset sum is in NP. But finding the solution is NP-complete.
Practice verify_subset function
Write verify_subset(arr, subset, target). Return whether subset's sum equals target. Print True with print(verify_subset([3, 5, 7], [3, 7], 10)).
Starter code
def verify_subset(arr, subset, target):
# Is subset's sum equal to targetSample solution
def verify_subset(arr, subset, target):
# Is subset's sum equal to target
return sum(subset) == target
print(verify_subset([3, 5, 7], [3, 7], 10))Expected output
True
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Reduction: match the terms
| Term | Meaning |
|---|---|
A → B |
Reduction |
polynomial |
Fast |
B solved |
A solved |
NP-complete |
Target |
2 How long does subset sum verification take?
- O(1)
- O(2^n)
- O(n²)
- O(n) Correct answer
Explanation: Verification is O(n); just compute the subset's sum.
3 Sum computation
return sum(____) == targetreturn sum(subset) == targetExplanation: subset is right.