Video 2-6: Karp-Reductions and NP completeness

0:03 In the next section, we'll look at reductions from one problem to another and then finally get to this notion of NP completeness. Again, recall we're looking at decision problems only. It's all about languages and machines that accept them. We've seen that example before. And we'll speak uh in terms of problems, we'll speak of things that are in the language as uh of yes instances where the answer is yes and otherwise no. Um in the TSP example, a yes instance is one where there is a tour that's less than capital D. Um a nitpick that I mentioned for for TSP but didn't go into detail is if we encode everything as a language, everything has to be a string. As I said before, computer science is all about turning things into binary strings. So that maybe isn't so surprising. Uh but whenever we have a problem that's defined on more abstract constructions like a graph or whatever else you can come up with, combinatorial um structures, you need to encode it as a string. But it's often enough to just use the standard data structures you learned in in undergrad data structures courses to represent things in a computer.

1:18 It's the same problem. You also have to represent a graph in computer memory that's effectively turning it into a string. So the same trick usually applies. Um the the thing to stress here is that n the input size we've always talked about really is the size of this encoding. So you have to be a little careful that the encoding is not completely nonsensical. If your encoding for the graph would be very wasteful, then you artificially blow up the input size and that might uh might give you uh strange results then for the running times. That's just a little caveat. What we'll come to now is this picture comparing nuts by hardness that we've seen before.

2:10 And the key definition for this is the notion of a of a carp reduction or a polomial time reduction or poly time reduction. This less or equal p where p stands for poly polomial time. So we have two languages a language A and a language B as up here. And we say that A is polomial time reducible to B. Bit of a mouthful that's why the abbreviation is often used. If there is uh a function that maps from the one language to the other language or from the the supererset from from the the alphabet uh of the two languages, it must be computable in poly time. So we have an algorithm that computes this function g. And now the crucial property is this uh for all words in the original in in this sigma star we have the word is in the language A if and only if the outcome of this reduction is in the language B and it's important that the implication goes in both ways right uh a word in a has to be if w is in a g of w has to be in b and vice versa for every Yeah, for every word not in A, G of W may not be in B. If you compare this with the intuitive notion, we're actually asking for something slightly stricter. Um or for this implication that any uh algorithm for B implies an algorithm for A, you could have allowed for example using an algorithm for uh or B as a subruine and call it several times. This we're not allowed to do here. We have to take the input, transform the input to a different input and then apply once the algorithm on the other problem and that's it. Also the output has to be the same. I cannot flip between one and zero. Yes and no. Uh that's what carb reductions do and uh that gives some nice properties um that go beyond this intuition. Uh the results I'm I'm not going to prove is is this. If if a reduces to b and b is in p then a is in p. And the same holds true for np.

4:33 Um these are all simple proofs. Um what it comes down to is that um right we need we need that definition though. We've defined a reduction. Now we need to define NP hardness and NP completeness that we haven't done yet. Uh but is is a simple definition based on these reductions. A language is called NP heart if every language in NP reduces to A. And that's a mouthful because you would have to somehow show that for every possible language in P in in NP and NP complete is the same plus we require that A is in NP itself whereas NP hard could also mean A is much much harder than NP itself. There are things outside of NP. uh we won't talk a lot about them or at least not now uh but there they are. Uh and so MP hard just means everything reduces to a nplete means a itself is in in NP as well. Uh and that's that's the key result that the intuition with the I can find a solution but neither can all these famous people that that relies on.

5:48 If I have an MP complete language any single problem TSP then this problem is in P has a poly time algorithm if and only if the whole two classes are equal all of the other problems also have a polomial time algorithm and um because we believe that that's not the case we shouldn't expect for an NPcomplete problem to find an efficient solution.

6:20 Again, I'm I'm going to skip this proof. It's not hard to do. Um, and instead, uh, I want to show briefly an example of a reduction.

6:29 Um, so looks like NP completeness tells us a lot. Do these problems even exist? Uh, it turns out that this is a transitive reduction. You can reduce all the problems to some problem A known to be MP hard and then do a single reduction that you have to prove. That's what you're going to do. And then you inherit that all these problems via A reduced to B. As long as we can find a single first NP hard problem, all further proofs of NP hardness can do a single reduction. That's what this slide says.

7:21 Um the cook leaven theorem means was the result that there is a first np heart problem namely the boolean satisfiability problem. You'll have to look at the definition if you don't know it. Um I'll I'll skip over that for now.

7:38 Um and the the proof here uses that you can use a boolean formula to simulate the computation of a Turing machine. Again, uh we don't have time to dig into this in in detail. If you want to read it in in full detail in slightly different languages, it's in the book. Um for those of you who can read German, um I wrote an algorithms book where that also has the proof uh spelled out, but it's in German.