0:00Last time we saw what a reduction is. It converts an instance of one problem into an instance of another, in polynomial time, and keeps the answer.
0:08A fast solver for B would give one for A, so B is at least as hard as A. To show a problem is hard, you reduce a known hard problem to it.
0:17This video is about which problems are already known to be hard. That's what the names NP-hard and NP-complete are for.
0:25To define NP-hard we start from NP. It's every decision problem whose yes answers can be checked in polynomial time, given a certificate.
0:33Shortest path is in it, since everything in P is in NP. So is SAT, which asks whether a logical formula can be made true, and so is three-coloring of a graph.
0:44This is subset sum from the first video. Does some subset of a list of numbers add up to a target?
0:50Every problem in NP reduces to subset sum. These three, and every other problem in the class.
0:57A problem with that property is called NP-hard. A polynomial time solver for it would give a polynomial time solver for every problem in NP.
1:05How can we know that every problem reduces to it? The first problem shown to be NP-hard was SAT.
1:12The Cook-Levin theorem rewrites any polynomial time check as a formula that can be made true exactly when some certificate passes the check. So every problem in NP reduces to SAT.
1:24After that, showing a new problem is NP-hard takes one reduction from SAT, or from any problem already known to be NP-hard. For subset sum, that reduction exists.
1:37Subset sum is also in NP itself. The positions are the certificate, and checking them is one pass.
1:44A problem that is NP-hard and in NP is called NP-complete, and that makes it one of the hardest problems in the class.
1:51Now take the halting problem. Given a program and its input, does the program ever stop?
1:56Every problem in NP reduces to it too, so the halting problem is NP-hard.
2:01But it isn't in NP. No algorithm decides it at all, so it is NP-hard without being NP-complete.
2:07Subset sum is one of many. Let's look at a few more NP-complete problems.
2:12The first is SAT. A formula is built from and, or and not, and the question is whether some assignment of true and false makes it true.
2:20Subset sum is the one we've been working with.
2:23Three-coloring asks whether each node of a graph can get one of three colors, with no edge joining two of the same color.
2:30And the decision version of the traveling salesman problem. Given cities, distances and a budget, is there a tour through every city within the budget? Each of these four reduces to each of the others.
2:42So take any one of them, say SAT.
2:44If someone found a polynomial time algorithm for it, every problem in NP would reduce to it. So every problem in NP could be solved in polynomial time, and that's P equals NP.
2:55Most researchers expect the classes differ, and in that case none of them has one. Decades of work haven't produced one either.
3:02NP-hard has one more use. It also covers problems that aren't decision problems.
3:07Take the traveling salesman problem. The version we listed was a yes or no question, whether a tour fits under a budget.
3:14The version people usually mean asks for the cheapest tour itself. That's an optimization problem, not a decision problem, so P and NP don't apply to it directly.
3:25It is at least as hard as the decision version, since the cheapest tour tells you whether any tour fits a budget. So we call it NP-hard.
3:33So that's the vocabulary: reductions, NP-hard, NP-complete. In the next video we take a problem that is NP-complete and look at four practical ways to deal with it.

NP-Hard and NP-Complete: The Problems Everything in NP Reduces To

Created by Abhyuday DesaiPublished 3 Oct, v1Runs 3 min 50 sec

0 views

About this video

In Episode 03 of P vs NP Explained, we define the two names for the hard problems. A problem that every problem in NP reduces to is NP-hard. If it is also in NP itself, it is NP-complete. Subset sum is both. The halting problem is NP-hard without being NP-complete, because no algorithm decides it at all. We then meet four NP-complete problems, and see why a polynomial time algorithm for any one of them would mean P equals NP.

You'll learn how to:

Define NP-hard and NP-complete, and tell the two apart
See how the Cook-Levin theorem made SAT the first NP-hard problem, and why every later proof takes one reduction
Recognize four NP-complete problems: SAT, subset sum, three-coloring, and the decision version of the traveling salesman problem
Understand why one fast algorithm for any of them would settle P versus NP
See why the optimization version of a problem is called NP-hard, though P and NP are defined for decision problems only

This video follows Episode 02, which explains reductions.

What changed

v103 Oct 2026abhydesai3 min 50 secab97bbc

First published version.

0 views0 likes on this version