# P, NP and Intractable Problems — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/a-classes

> Recognise exponential problems, pseudo-polynomial algorithms and the P vs NP question.

## 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?

```python
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.

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

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

*Answer:* Its running time is polynomial in the value W, but exponential in the number of bits used to represent W. Input size counts the digits of W, and W can be exponentially large in that digit count.