0:00Last time we saw what NP-complete means. Every problem in NP reduces to an NP-complete one, and none of them has a known polynomial time algorithm.
0:10Suppose the problem you need to solve turns out to be one of them. The first response is to search anyway. When the inputs are small, the exponential algorithm is fast enough.
0:20So measure how your real inputs behave before deciding that the search is too slow.
0:24Twenty numbers give two to the twenty subsets, roughly a million, and a computer gets through that in a second or two.
0:31The second is to use something specific about your problem. Subset sum has a feature like that, and we'll see it in code in a moment.
0:39The third is to accept a good answer instead of the best one.
0:42And the fourth is to hand the problem to a solver that people have spent decades tuning. We come back to these two after the code.
0:49Let's look at the second strategy in code.
0:52This is the whole program. One function, and two calls at the bottom.
0:57This is a dynamic program. Instead of trying subsets, it tracks which sums can be made from the numbers seen so far. It starts with just zero, the sum of the empty subset.
1:08Then for each number, it takes every sum already reachable, adds the number to it, and keeps those new sums as well.
1:14At the end, the answer is whether the target is one of the reachable sums.
1:18At the bottom we call it twice. First on one, two and four with target seven, with show switched on so it prints the set after each number.
1:28Then on the numbers one to thirty, with target one hundred.
1:31Let's run it.
1:33We run the file with Python.
1:35The first three lines are the traced run, and then come the two answers.
1:38After the number one, the reachable sums are zero and one.
1:42Adding two to each of those gives two and three, so now there are four sums.
1:46And adding four gives every sum from zero to seven.
1:49Seven is in the set, so the first call answers yes.
1:52The second call was thirty numbers with target one hundred, and it also came back at once. Trying subsets would have meant about a billion of them. Let's see why this one is fast.
2:04The reason is one line in the loop that we skipped.
2:07Every sum it keeps is between zero and the target, so the set never holds more than target plus one values. Each round does at most that much work, and there is one round per number.
2:18Thirty numbers times about a hundred sums is a few thousand steps. The running time is polynomial in the value of the target, and that's called pseudo-polynomial time.
2:27The pseudo is there because the value of the target is not the size of the input.
2:33The size of an input is the number of bits it takes to write it down. A target is a number, so its size is the number of bits in it.
2:40With seven bits the largest target you can write is one hundred twenty seven. Add one bit and it's two hundred fifty five, so the set the algorithm tracks can be twice as large.
2:49The work doubles with each extra bit, and that is exponential in the input size. That's why this algorithm doesn't put subset sum in P.
2:58It does mean that a small target makes the problem manageable, and that's the structure the second strategy uses. Let's go back to the list.
3:06So that's the second strategy, with its condition. The dynamic program is exact, and it's fast as long as the target is small. The other two strategies are more general.
3:17The third strategy is for the optimization versions, like the cheapest tour. Instead of the best answer you take a good one, quickly.
3:24An approximation algorithm comes with a guarantee, within some factor of the best possible. A heuristic doesn't, and is often good anyway.
3:32Either way, when a heuristic improves a tour step by step, it has found a better tour. It hasn't shown that no better one exists.
3:40The fourth is to hand the problem to a solver. SAT solvers and integer linear programming solvers, ILP for short, have decades of engineering behind them. Translating your problem into their format is itself a reduction.
3:55Their worst case is still exponential, so you test them on instances like the ones you'll actually see.
3:60So those are the four. What's left is how to pick one.
4:03When a problem turns out to be NP-complete, the theory tells you one definite thing. Don't expect an exact algorithm that is fast on every input. What you do next is a practical decision.
4:16It depends on how large your real inputs are, whether an approximate answer is acceptable, and how much time you have to spend.
4:22That's the end of this series. We covered what the two classes mean, how reductions carry hardness between problems, and the two names for the hard ones. Thanks for watching.

Your Problem Is NP-Complete. Now What?

Created by Abhyuday DesaiUpdated 4 Oct, v2Runs 4 min 38 sec

0 views

About this video

In Episode 04 of P vs NP Explained, the problem you need to solve turns out to be NP-complete, and we look at four practical responses. Search anyway when the inputs are small. Use something specific about your problem. Accept a good answer instead of the best one. Or hand the problem to a solver. For the second, we run a dynamic program that answers subset sum for thirty numbers at once, and then see why that doesn't put subset sum in P.

You'll learn how to:

Measure how your real inputs behave before deciding that an exponential search is too slow
Read a dynamic program that tracks the reachable sums, where trying subsets would mean about a billion of them
Understand pseudo-polynomial time: the work is polynomial in the value of the target and exponential in the number of bits it takes to write it
Tell an approximation algorithm, which comes with a guarantee, from a heuristic, which doesn't
See when to hand a problem to a SAT or integer linear programming solver, and why you still test it on your own instances
Choose between the four by input size, whether an approximate answer is acceptable, and the time you have

This video closes the series. The code runs from the companion repo.

What changed

v204 Oct 2026abhydesai4 min 38 sec04af2da
Re-recorded so the solver line in "Approximate and delegate" uses the narration clip that says ILP as three letters; the previous take had played a clip synthesized from the raw pronunciation mark. The reachable-sums and the-bound code scenes were recompiled, hanging a terminal highlight's label below a box that sits at the top of its panel.

Same chapters. Transcript: 1 of 40 lines changed.
Show the differencesHide the differences
1. The fourth is to hand the problem to a solver. SAT solvers and integer linear programming solvers, {ILP|I-L-P} for short, have decades of engineering behind them. Translating your problem into their format is itself a reduction.
  
  The fourth is to hand the problem to a solver. SAT solvers and integer linear programming solvers, ILP for short, have decades of engineering behind them. Translating your problem into their format is itself a reduction.
0 views0 likes on this version

v103 Oct 2026abhydesai4 min 39 secab97bbc

First published version.

0 views0 likes on this version

Watch v1