NP-complete

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.

Exercise 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)).

Show example 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))

Test yourself

Subset sum

subset_sum([3, 5, ____], 10) → True

Show answer

subset_sum([3, 5, 7], 10) → True

Which class is subset sum in?
- P
- Logarithmic
- NP-complete
- Constant time
Show answer

NP-complete — Subset sum is NP-complete.
NP-complete: match the terms

NP-complete

Hard
brute force

2^n
subset sum

Example
P=NP

Open

Next lesson: Reduction

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies