Video 2-7: Karp-Reductions and NP-Completeness

0:03 uh in the next section we'll look at reductions and NP completeness completing the picture of of uh classic complexity theory that we've started with with the formal definitions. Um remember all we talk about when we say algorithmic problem in this context is a decision problem. At the end of this uh unit we'll come back to other types of problems. So all we all we ask is always is a certain string part of a language. um from some some alphabet and we can use this to encode typical algorithmic questions when they have a yes no answer. For example, this traveling salesperson example, we've we've seen that before. The threshold problem where you give uh a bound on the tour length an instance um a word is in this language if it encodes a valid instance and there is an optimal tour up to this uh length capital D.

1:01 So we can uh restrict ourselves to these languages. That's um what this means for now. And uh we say w is a yes instance if it's in the language otherwise a no instance. I guess all of this is rather um rather intuitive. Uh sometimes when we work on uh more complicated structures the encoding may be less trivial. We have to think about how to do this properly. And for for things like graphs uh usually you get by with just any standard data structure as long as you don't care about polomial overhead. Usually you can do either uh of these representations and just convert them to any that's more convenient to work with. So all of this will be um mostly irrelevant. Still you should remember that n is always this this length of the encoding not maybe a more convenient parameter in in a graph and you have to reme keep in mind that the two may not always be the same even though usually they're polomially related and then it doesn't matter.

2:15 Okay. Okay, so so far uh we've seen we've defined these classes and we can now wonder how would I prove that a certain problem is uh in NP but maybe not in P and as you know we don't really know a good way uh not a definitive proof anyways um all we can do so far is compare problems and the intuitive version remember the nuts picture that came up uh before.

2:46 So the formal version of that is a polomial time reduction and we'll write this as this lesser equal p for polomial right. Uh formally you have two languages they could be over a different alphabet if you insist and we say that a lesser equal p you should read this as a is easier than b. So this lesser equal is in terms of hardness complexity. So um a is poly time reducible to b. If there's a a total function that takes any word that could be in language A and maps it to a word that could be in language B where we have the precise equivalence that if a word is in A, G of d of that word must be in B and vice versa. Uh note that G may not be sjective. So there might be some words that could be in B that we never asked the question about. And that's the case where B could be much harder than A. We're only looking at a sub problem, the image of G uh in in B. And there might be other cases that are I don't know arbitrarily hard or whatever else in B that we don't look at.

4:08 Okay, this is known as carp reductions or um just polomial time reductions. This is the standard notion. Um this is indeed a bit stricter than what you would maybe come up with if you just want the intuitive version above here that any polomial time algorithm for B immediately implies one for A. For that it would be fine to say uh allow a negation here or it would be fine that you call uh assuming a hypothetical algorithm for B, you could build one for A that calls this algorithm for B many times. All of these things would still serve this implication. We forbid them for structural reasons. This is much stricter and it allows a finer distinction between problems. in particular then uh the distinction between NP and co-enps problem from the question before that's an element of co-enp state co-enp is precisely the problems where the complement problem the uh complement language is in is in P in NP it's a set of all languages so that the complement is in P in NP keep saying P and we've seen one example answer where this is this is still a natural and sensible question to ask okay so that's why people define polyon reductions with this slightly stricter notion.

6:01 Okay, then we can deduce a few things that people may know. If uh a can reduce to boly time reduces to b and we know that b is already an easy question or b is in np then it follows that a is in the same set.

6:25 The proof is easy. If B is in P, there's a polomial time algorithm to decide that uh that has the right language. And this reduction implies that there's this function G that maps uh words in the supererset of A to something supererset of B. So that words in A are precisely mapped to words in B. Uh and then this function is poly time computable. Well, that means there's a machine that does it. Okay, there's a two turing machines now that we can put together. We construct a new taring machine M prime for this for this problem for this language A which first simulates G on the input which produces an output right the image G of W and then runs this machine M that decides B and we just output the same whatever M says we also output and of course that does exactly the right thing.

7:29 If you replace polomial time deterministic here, if we don't say anything, deterministic is the default. If you insert nondeterministic here, the rest of the proof is the same. So that also proves um this relation with with NP. Okay. Um what else? Based on that, we can define these notions of hardness. the hardest languages in a certain class. So a language is called NP hard if for all languages in in NP it's true that they reduce to a. So in a way you can think of the the pile of of hard problems and uh climbing up means the problems get harder and in some sense this problem a sits here if it's np hard it is maximal in the sense of this of this uh lesser equal p but we'll see that this is not there's not a unique peak that's why rather draw u draw a plateau here. And the second term NP complete is NP hard plus the problem is also in NP. NP hard could essentially mean that we also include problems outside of uh NP and here the intersection is NP complete.

9:11 Not one line. Okay, I guess this is also known. Why are these definitions useful? Well, they imply the following cool theorem. If you have any nplete language A then it's the same thing to ask whether this particular problem can be solved in polomial time or whether P and NP are just all the same which means all these problems in NP that we don't know algorithms for are poly time solvable. Of course we don't really believe that or it seems a bit much to ask for at least in a constructive way. So the the consensus hypothesis say is that this inclusion is strict. P is not the same as NP. And so uh by uh using this in reverse we should for no nplete problem expect a general efficient solution in the sense of polytime during machine right with all remember the loopholes all the caveats worst case deterministic yada yada yada okay uh the proof for this theorem is also rather easy.

10:23 If we have an arbitrary language that's the implication to the right. So assume a is inpart. If you have any other language that is in np then by hardness we know that l reduces to a but also a is in p. So uh by the lema from the slide before right one more slide before this already means that B is also NP and so uh L was an arbitrary language from NP. So the two are equal.

11:05 And conversely, well, if the two are the same, then anything that is NP complete is also in NP, which is the same as P. So, um, even A is NP.

11:22 If I'm going too fast, let me know. Um, but my feeling is this is rather wellcharted territory for you. But uh speak up if if it's too too rushed.

11:36 Uh of course keep always keep in mind what NP completeness thus means. It tells us a lot about this problem because uh it's essentially making it the same to ask that this problem is in P then P= NP altogether. So how can we possibly prove such a thing? sounds uh rather challenging and indeed it isn't easy to prove. Uh so let's do it only once and otherwise uh just translate it. If you have some problem A that you know to be NP hard the coconut then a single reduction a single arc or a single proof of such a lesser equal P relation to your new problem that you're interested in now immediately gives you that the problem is NP hard because you can chain together the reductions. That's a property of polytime reductions that maybe um is is not completely obvious but it has to do with the fact that uh adding up polomials remains polomial.

12:40 Uh so whenever you start with an arbitrary language here and you want to use this this poly time reduction suppose that there's an algorithm for for B then I can take the reduction that transforms an input for L to A then I take the second reduction to take the output of that thing and I transform that to an input of B. Now in in this step I might make the input polomially bigger. That is a subtle consequence of how we defined this reduction that maybe is is worth pointing out briefly.

13:22 The way here it doesn't show up in the definition at all because it's implicit. Um but the fact that this function is polomially polomial time computable this also implies that the length of the output because I have to produce it is less or equal some polomial in the length of w I don't need to say that explicitly because if it can be computed in polomial time I just don't have time to create more junk so to speak But of course this is very useful in this reduction now because that means if I start with some input for L I might make it polomially bigger as a an instance to A and then I make it polomially bigger again turning it into an instance for B. So I'm taking one polomial and insert it into another polomial but that remains a polomial. I might go from n to n to the 10th and I take n to the 10th and put another power to the 10th. That's n to the 100th. It's not great, but it's still polomial.

14:34 Okay. So what we used here is that if you take a polomial and insert it into another polomial you get another polomial. Let me write it informally like this. That's what's behind this.

15:07 Okay. And that that means if a problem is np hard and a reduces to b then b is np hard. That's the usual way how we prove hardness. And it relies on this on this uh stability of polomial time reductions. Um since people know formulas, shall we skip this? So this is asking you to evaluate a boolean formula here for specific sets uh for a specific assignment.

15:40 I mean, we can do it if uh it gets you into thinking about the satisfiability problem. Maybe it's useful. Now the first um may be true about this formula. I mean it is true about this formula. The specific question is a bit picky. it asks for the specific value under this assignment and that's always a boolean value true or false. Um whereas satisfiable is really a property about just the formula without an assignment. I don't think we need this nitpicky distinction really but uh just in case.

17:07 Now maybe uh one one sentence how how do you evaluate a formula like this? So uh I put x1 equals true. So I have true and perfect. So whatever the value of the second thing is will be the output. Now x2 is true but I say not x2 that's a false and x3 is false. So it's false or false that remains false. So sadly the whole formula is also false or I mean sadly whatever maybe it's good that it's false. Who knows? That leads me to this last part. With these reductions, we need one place to start in a way the mother of all NP hard problems or npmplete problems and that is the satisfiability problem. And then there's uh the famous theorem by Cook and Levvin that SAD is indeed nplete which means it it can simulate any Turing machine. What is the satisfiability problem formally? So I'm given a boolean formula such as the example we've seen on the previous uh question and um it has some variables x1 up to xn and the question is uh can I find some way to put these variables to true and false that makes the whole formula true and u it's it's important that this is an exist existential question it does there exist one such assignment yes or Oh, that makes the formula true. And uh so you see the NP nature lurking through. It's easy if you give me an assignment to write a verifier that just plucks in the values in the formula and evaluates it. And then you get the uh the answer whether that certificate works or not, if it makes the formula true or not. But the converse is kind of hard to imagine how to do it. And indeed, you're not alone with struggling to imagine how to prove that a formula is not satisfiable by writing down some short small thing.

19:10 I'm not going to go in a full proof of this theorem, but the whole point of defining Turing machines so diligently is to make that proof rather easy.

19:22 So, um, how would you conceptually do this? I don't know have people seen this proof in some lectures is a bit 50/50 whether people do it. I feel is it's very unsatisfying to do all these reductions from a problem that you have no idea how it happens to be hard. So let me try to give very high level the idea. What do we need to show? Well in NP I've already argued that's the trivial part. guess an assignment and and check or given an assignment verify uh the other direction the hardness um the other part the hardness is the interesting bit I'm given any language in NP so that means there is some nondeterministic Turing machine that accepts precisely this language L and so I'm I'm supposed to somehow encode that as a formula now the trick is the formula can be much longer than this machine it can be polomially long and we'll use that power fully.

20:24 Um the easiest to think about is the variables for the formula. First of all, uh does it say poly time anywhere? Uh okay, not not really. I mean the construction works in general, but we know that for our M here, it must be a polytime Turing machine. Otherwise it wouldn't show that n is in np.

20:53 That means there's always some upper bound for the running time or any uh specific let's say we use capital t to denote this upper bound that we know for m on the input of our um word w.

21:21 yeah it's specific for a given word of course. So we're given some word to check in np. Now I can work out how many time steps this Turing machine M can potentially take. That's my capital T. And then I'm going to just encode in variables anything there is to know about a potential computation of this machine. For example, I can ask is the machine at time t in a given state Q. Yes or no. That's one variable. I can have a variable that tells me the tape contents. Given that the time the machine only has time capital T, it will only fill the tape with chunk of size T. It can't reach more of the tape. So for each of these positions I so again I is essentially bounded by T and T is bounded by a capital T and the character is well this is a finite alphabet that's small anyways. So I can I can write down a variable does this cell of the tape at this point in time contain this letter yes or no. And lastly, I can uh uh encode where does the machine look at this point in time.

22:38 Does the machine look at this cell I at time point t? Yes or no? That's a lot of variables. But note that it's only polomially many because all these uh indices are bounded by some polomial or are bounded by this capital t. Now I haven't told you how to encode the rest. This is not a formula. This is just variables. But maybe you can think about how the rest would look like. What you have to do is for all these variables, write a lot of clauses that tell you if the machine at this point in time is at a certain position and it reads a certain letter at the tape and it's transition table tells me well with that combination of state and and red input, I'm supposed to move left. Then for example this this variable set for the next time step needs to be one less. So I I imply that set I minus one t is true. So you can write a long long list of implications of this form. If the machine is in a certain position at a certain point in time I know what follows.

23:46 And you can write this even for nondeterministic steps. Uh if you say that um I'm I'm allowed to be in several places. Okay. Um then you wouldn't write it as an as an implication but rather uh backwards. If I'm now in a certain state, I must have previously been in an allowable previous state, not forward in time, backward in time. So you get this really huge formula but also these kind of conditions to tie the variables together are bounded by some function in t. And so it remains all the polomial time reduction that for this specific word you can construct a very large formula that just encodes is there some way for my touring machine to arrive at any point in time at a halting state with a nice uh one in the tape left of it. It's not exactly uh practical, but it proves that you can simulate any Turing machine. And so uh SAT is as hard as all of NP.