0:00Last time we defined two classes of decision problem. P is the problems you can solve in polynomial time, and NP is the ones where you can check a certificate in polynomial time.
0:10Whether the two classes are the same is an open question, and most researchers expect that they aren't.
0:17This video is about reductions, the way one problem is converted into another. That's how hardness passes between problems.
0:24Let's start with what a reduction is.
0:26Suppose we have a decision problem, call it A, and we're given one instance of it to answer.
0:31A reduction is a procedure that turns our instance of A into an instance of problem B, a second decision problem.
0:38The conversion is an algorithm in its own right.
0:40And it has to run in polynomial time, so the conversion is never the expensive part.
0:45It also has to preserve the answer. If the original instance is a yes, the one we built is a yes. If it's a no, the one we built is a no.
0:54Now suppose somebody hands us a solver for problem B.
0:57We give it the instance we built, and it returns a yes or a no.
1:01And because the reduction preserves the answer, that yes or no is also the answer for our original instance.
1:07So B's solver has solved A for us, with a polynomial time conversion in front of it.
1:12This is written with a less than or equal sign carrying a small p, for polynomial, and read as A reduces to B.
1:20It's a statement about hardness. A fast solver for B would give a fast solver for A, so B can't be easier than A.
1:26To show a new problem is hard, you reduce a problem already known to be hard to it. Hardness travels with the conversion, from A to B.
1:34Let's put two real problems into this picture.
1:38Say A is exam timetabling. We have a list of exams, and some pairs clash because a student is taking both. Can we fit them into k time slots with no clash?
1:47And B is graph coloring. Given a graph and a number k, can every node get one of k colors so that no edge joins two of the same color?
1:55The conversion makes a node for each exam and an edge for each clash. Fitting the exams into k slots is the same question as coloring that graph with k colors.
2:04Then we run the coloring solver on the graph.
2:06Its yes or no is the answer for the exams, and if it also returns a coloring, each color is a time slot.
2:13In practice, this is how you reuse a solver. What it shows about hardness is that coloring is at least as hard as timetabling. A fast coloring solver would give a fast timetabling solver.
2:24It says nothing about whether timetabling itself is hard. For that, you'd reduce a known hard problem to timetabling.
2:30That's what a reduction is.
2:32The conversion runs in polynomial time and keeps the answer, so whatever reduces to a problem can't be harder than that problem.
2:40So which problems are already known to be hard? In the next video we answer that with two names, NP-hard and NP-complete.

What a Reduction Is: How Hardness Passes Between Problems

Created by Abhyuday DesaiPublished 3 Oct, v1Runs 2 min 53 sec

0 views

About this video

In Episode 02 of P vs NP Explained, we look at how one problem is converted into another. A reduction takes an instance of problem A and builds an instance of problem B, in polynomial time, so that the answer stays the same. A solver for B then answers A as well. We work one example through: exam timetabling becomes graph coloring, with a node for each exam, an edge for each clash, and a color for each time slot.

You'll learn how to:

Name the two requirements of a reduction: the conversion runs in polynomial time, and it preserves the yes or no answer
Read "A reduces to B" as a statement about hardness: B can't be easier than A
See why showing a new problem is hard means reducing a known hard problem to it, and not the other way around
Follow exam timetabling being converted into graph coloring, and read a coloring back as a timetable
Understand what that reduction shows about coloring, and what it leaves unsaid about timetabling

This video follows Episode 01, which defines P and NP.

What changed

v103 Oct 2026abhydesai2 min 53 secab97bbc

First published version.

0 views0 likes on this version