P, NP and Intractable Problems

When no fast algorithm is known

Problems solvable in polynomial time, O(nᵏ) for some constant k, form the class P and are considered tractable. NP is the class of decision problems whose solutions can be verified in polynomial time: given a proposed route, you can quickly check that it visits every city within a distance budget. NP-complete problems are the hardest in NP: if any one had a polynomial algorithm, all NP problems would, which is the famous open question P vs NP. Examples include Boolean satisfiability (SAT), the decision versions of the travelling salesperson problem and graph colouring, subset sum and 0/1 knapsack. Brute-force solutions examine all subsets (O(2ⁿ)) or all orderings (O(n!)). Some have pseudo-polynomial dynamic programming solutions: 0/1 knapsack in O(n · W), polynomial in the numeric capacity W but exponential in the number of bits needed to write W. In practice, engineers handle such problems with small inputs, approximation algorithms, heuristics, or specialised solvers.

Brute force versus pseudo-polynomial dynamic programming

Subset sum: does any subset of nums add up to target?

from itertools import combinations

def subset_sum_brute(nums, target):
    n = len(nums)
    for r in range(n + 1):
        for combo in combinations(nums, r):   # 2^n subsets in total
            if sum(combo) == target:
                return True
    return False                              # O(2^n * n)

def subset_sum_dp(nums, target):
    reachable = [False] * (target + 1)
    reachable[0] = True
    for x in nums:                            # n items
        for s in range(target, x - 1, -1):    # target + 1 sums
            reachable[s] = reachable[s] or reachable[s - x]
    return reachable[target]                  # O(n * target): pseudo-polynomial

Exponential is fine for tiny n

2²⁰ is about a million, so trying all subsets of 20 items is quick. Interview constraints like n ≤ 20 are a strong hint that a bitmask or backtracking solution is expected.

Quick check: Why is the O(n · W) knapsack algorithm called pseudo-polynomial?

• It runs in O(n) time
• It only approximates the answer
• Its running time is polynomial in the value W, but exponential in the number of bits used to represent W
• It requires quantum computers