NP-complete
- Algorithms course
- Expert
- Lesson 6/41
- 4 min
Properties of NP-complete problems.
NP-complete
A problem is NP-complete if it is both in NP and NP-hard. All NP problems can be reduced to it in polynomial time.
If an NP-complete problem is solved in polynomial time, all NP is solved in polynomial time; that is, P=NP.
Brute force
Subset sum is an NP-complete problem. The simple solution tries all 2^n subsets; this is O(2^n).
For small inputs brute force works. For large inputs, approximation algorithms are needed.
Practice brute_force_subset function
Write brute_force_subset(arr, target). Try all subsets, return whether any sums to target. Print True with print(brute_force_subset([3, 5, 7], 10)).
Starter code
def brute_force_subset(arr, target):
# Try all subsetsSample solution
def brute_force_subset(arr, target):
# Try all subsets
n = len(arr)
for mask in range(1 << n):
s = 0
for i in range(n):
if mask & (1 << i):
s += arr[i]
if s == target:
return True
return False
print(brute_force_subset([3, 5, 7], 10))Expected output
True
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Subset sum
subset_sum([3, 5, ____], 10) → Truesubset_sum([3, 5, 7], 10) → TrueExplanation: 7 is right.
2 Which class is subset sum in?
- P
- Logarithmic
- NP-complete Correct answer
- Constant time
Explanation: Subset sum is NP-complete.
3 NP-complete: match the terms
| Term | Meaning |
|---|---|
NP-complete |
Hard |
brute force |
2^n |
subset sum |
Example |
P=NP |
Open |