Video 3-4: Strong NP hardness

0:03 We've seen some problems where we could find pseudopolomial time algorithms but also there's many many other problems where nobody has succeeded. So we want to complement this nice algorithmic design technique with a lowerbound an impossibility technique and that's called strong np hardness. I think I apologize for the name even though it's not mine of course. uh in light of the later theory, you'll see that this is a bit of a a bold name for a rather limited concept. It just predates some of the other developments and so people coined the term when there was a lot of terms available. Maybe um in hindsight is is not great. Uh maybe what we would want to say is is even uh hard for small numbers or something like that that conveys a bit more the message. Um let's start with the definition straight away from what you've seen maybe you can guess we should somehow express that a problem remains hard even if the numbers are are small because then a pseudopolomial time algorithm uh can't exist right this is the intuition I think is clear if um if an algorithm is only exponential in the size of in the value of these numbers and the problem is start even with small numbers well then probably you don't have such an algorithm formally um and note that I've I've um I've renamed the variables is kind of if you want to check I've updated this consistently retroactively in in unit two as well I want to be a bit more strict about talking about problems which are always denoted by pi for problem um versus just the language for decision problems was a bit in clash with the optimization version. So L was used for two different things and I didn't like it after after all. Um so we the notation will always be for decision problems that pi is a universe L and then you have the subset of yes instances denoted by Y. Hopefully that's that's more intuitive.

2:25 So L would be the universe of allowed inputs for this problem. the things that type check or that properly decode into a sensible input nothing fundamental otherwise has changed in the definitions but I think the names are more consistent that way and so many of the definitions now you can read for both this decision and for optimization versions uh let's let's focus on decision versions um the problem is called strongly np hard if there's some polomial p so that uh this lovely restriction is np card.

3:24 Um, I somehow lost the formal definition for that that uh I would have wanted to have somewhere on the slide. Was this in the beginning?

3:47 That would certainly be the case. Yeah, this one. Um, let me copy that to the to the slide where it's relevant. Again, we've talked about this when the notation uh uh wasn't fully settled. Maybe So this is the the problem of all the instances where maxin is small and if that remains np heart then we call the whole problem strongly np hard. Okay, of course the intuition precisely what we said earlier and let's quickly formally prove that this does what it's supposed to do which means if we have or assuming P is not NP and we have a problem that's strongly NP hard then there is no pseudo polinomial time algorithm that's the statement we want that we want the definition to reflect right well by definition If this problem is strongly NP hard from the previous slide, it means there's a value restricted subpro or a polomial P that remains NP hard. Again, see how lovely this is that we can essentially read this for optimization and decision versions. But let's just focus on decision versions.

5:18 Um so you can restrict the problem to only those instances with a small with with a max in bounded by some by this polinomial p and it remains a hard problem. Okay. Then let's make a contradiction out of this assumption. Assume there was some pseudopolomial time algorithm for this problem. So there is a certain time function for this that on any inst any instance x that we have in L the time of this algorithm is bounded by this other polomial Q and this is bariate it's bounded in it's a function of this input encoding size and the maximum integer inserting the definition of pseudo polomial nothing else has happened and now we're going to use um the statement about polomials we've used before. If I take one polomial and I plug in another one, the result is again another polomial with larger larger exponents.

6:19 Um the formal statement for any input in our value restricted problem, we know that the max int is restricted by this polomial P, right? And so if I insert that into here, I just get that the time for this algorithm is polomial. But that means I've built a poly time algorithm for an NP hard problem. So assuming that P is not equals NP that cannot be hence such an algorithm. Oh one more one more slide. So that's a contradiction to the fact that P is not equals NP. So no such algorithm can exist. Okay. So this is the right notion of hardness for pseudo polinomial algorithms. If you want to show a pseudopolomial algorithm doesn't likely exist, you should try to prove hardness for small numbers. Strong strong strong hardness.

7:16 Uh let me mention just because this is freaking confusing. There's a different notion that's called strict strictly NP hard. I guess same adverbs here and this is is rather annoying. Um strict np hard is that you're uh you're doing um a polomial number of arithmetic operations no regards to how big the numbers are. So it's somewhat related. So okay the hardness means strictly polomial is the interesting statement is the open question for for LPS. Okay, I'm this is kind of besides the point. I just want to mention there's another another term that's rather close linguistically but is a separate concept. Again, not a great name in my opinion. Uh this has to do with the fact can you solve linear programs in um in polomial time with with good guarantees on the numbers or the stability or do you somehow need to need to have numeric in there? This is uh maybe we can come back to this when we talk about LPS. For now, let's just uh fix that this is a different thing and strongly NP hard is what we care about here. A very simple notion [snorts] and let's see some example uh at least one and you'll do some more maybe in the tutorials that uh the traveling things the TSP problem traveling per traveling salesperson is strongly NP hard. What do we have to do? Well, show strong NP hardness is a normal NP reduction just that now the target problem the new problem is this value restricted traveling salesman problem and the the only kind of creative insight you need is how do you restrict it and here it turns out the it's sufficient to say a linear upper bound the polomial can even be very small we're only looking at instances of the trailing salesperson problem where all the numbers are at most n at most the the input size or say the number of vertices in your the number of cities in your input even formally speaking this this n here is the length of the entire input the number of cities will be less than that what we actually use is just the number of cities both will be fine and then the reduction maybe you can guess what this what this does uh from Hamilton cycle So, Hamiltonian cycle again is this question.

10:11 Um, you know, let me use another little gimmick for this. If you ever feel like you're forgetting the definition of these NP hard problems that we discussed in the last unit, uh there's a a little animated list of all of them. And Hamiltonian cycle here we can use the undirected version. um has a graph as input and uh the question is whether you can find a tour that is vertex simple and visits every vertex.

10:55 Is there a vertx simple cycle in G that visits every vertex of length exactly V of G and there's a a specific example etc etc and you can uh even have different certificates right is not a unique question the whether this website is useful to anyone I don't know um I felt we at some fixed specific uh definitions and I was very tired of scrolling back in my own slides.

11:32 Either way, that's the Hamilton cycle problem. So, how can we embed that in the TSP problem? Well, rather easily. Given a graph for the Hamilton cycle problem, we output distances for the TSP problem where every edge gets distance one and a non-edge gets distance two.

11:53 So now a Hamilton cycle means I'm traveling through my graph using only proper edges. So I will have distance exactly n. And um if I can do that somehow then I have a a Hamilton cycle. So if I ask for the threshold n either there is a tsp tour that uses only edges in the original graph then it's a yes instance or if um if not then any tsp to must use some at some point some non- edge and will be above n plus will be at n plus one or above.

12:40 And here you can even do both directions in one. Right? This is easy enough uh correspondence. Okay. So we've shown that this value restricted problem is still NP hard. Hence TSP is strongly NP hard.

12:58 Let's have a few others. Um for some of which you can guess it from what we've seen from others. um you don't really have more than your gut feeling to go by and for some others you'll see them again. Um I think some of them were mentioned on the slides but I I didn't spend a lot of time uh explaining them. So take the question as rather at this point in time what's your gut feeling about the problems? You'll again we'll revisit it in the tutorials.

14:10 Don't call me out for being now I've been a bit vague at the beginning of this chapter saying what an integer value uh an a number problem is.

14:20 What was the what was the formal phrase? an integer input problem and I think now we're using this uh a bit informally but still all of these problems have some number in their input. So formally it's correct.

14:39 I wouldn't call vertex cover an integer input problem really because it's it's a graph and not really numbers but of course there's the threshold. So any decision problem coming from an optimization problem has an integer in it.

14:54 Okay. Uh anyone still busy typing and let's see the votes. Okay. Rather clear picture. Um, let's go through them before before I reveal the answers. Right. So, for vertex cover, how would you argue? Most seem to think it's hard. So, maybe someone wants to quickly say why weights. So, >> but that's always small, right? And so, yeah, uh is a rather boring one. The next two you'll see some you'll see again soon, so let me not spoil much about them. Uh TSP, well done. you've remembered from the previous slide. Binacking is a more interesting one. Um there maybe it needs a bit of a thought. Also, your questions were your your votes were a bit right. Um who's in favor of hard at least one person voted it. Who's in favor of pseudo polomial algorithm exists?

16:31 So, um maybe let's let's leave that one open. We'll come back to that one eventually and you can think a bit bit more about it. Um once you know which way to argue, it's rather easy. So maybe you can figure it out. It's maybe on the spot a bit hard if you've not seen it.

17:05 Keep up the tension. Okay. One thing we can um we can do to the definition of strong anti hardness is modify modify it slightly so that sometimes it has a form that's a bit more convenient. That's the last thing I want to add to this. Um it's the same thing as asking so strongly NP hard is the same thing as insisting that the numbers are encoded in unary and the problem uh still being hard. So that's formally written there. What what I mean by unary encoding? Well, uh writing the number 1,00 you do 1,000 ones and then a zero. It's like uh the literal making ticks over the number. That's of course completely stupid and inflated. But that's precisely the point, right? We make the input artificially big. And if that if you can do that to a problem inflate n so much and it's still hard then probably all your numbers were not too large to start with in a way. Uh so maybe it's not surprising that these are the same. Let's formally argue it either way. So if if a is strongly np hard that's the one one direction then there is a polomial so that the this algorithm uh there's this um problem restricted to max int I guess this wants to be a pi of course it's just a local variable so it doesn't matter so the problem restricted to this polomial size max is still n hard then if we apply this unary encoding not that much happens the input is only a polomial factor bigger and so uh it remains an NP hard problem just because you haven't changed the input size by much it's a polomial it's a poly time reduction to take the input and replace every number with its unary encoding and conversely if you have this problem with unary numbers and you know it's np hard then trivially this max info function is now a bit stupid because you need as many bits to write down the number as it is large. So max is always bounded by by n and so uh the restriction of this problem by a polomial leaves the problem unchanged.

19:33 So saying that it is hard with unary numbers means it's np hard by definition already. Okay. So these two things this is a superficial rewriting but sometimes it's a bit uh more convenient to state that you you need to give weights in unary. Let me give you a concrete example where this is maybe not that unnatural. Think about shortest paths in a graph. Now this is not an a famous npart problem but uh for the sake of the argument say we stay with shortest paths. If all your edge weights are integers, you could replace an edge of length five by subdividing it four times with little vertices. So that now is a a path of length five. Then you can forget about the weights of the edges, but you've blown up your graph in the same way as if you had written down the numbers in unity. So in a way it's simulating constructions like this. And sometimes that's just a more natural way to go.

20:36 Okay, last one of these fun questions. This is really just a attention test and definition cache test. Are we waiting for number four? Okay, there we go.

21:54 So, the majority called it. Um now essentially this is just disentangling the definitions. If you take the knapsack problem and you encode the numbers in unary that's the same as saying you take the input size and restrict max int to be linear and uh we've seen a pseudo polomial time algorithm which then becomes polomial time if you encode the numbers in unary. That means we can solve the problem to optimality in polomial time. That means it's uh as an optimization problem it's in this class PO the optimization problems where I can find an optimal solution in polinomial time. Okay.

22:39 So to wrap up on on this chapter um we've seen polinomial time algorithms that can work well because they're simple DP algorithms. If the numbers are indeed small that's efficient or as efficient as dynamic programming with the uh superlinear polomial time can get but it is a bit restricted there's only a handful of problems where this seems to work the only non-trivial example that I know of where you get pseudo polomiality which which is not directly a a DP in disguise is for factoring polomials. This seems to be dependent on the total degree of the input in a in a pseudo polomial way. So you can do it if the polomial is large if it's multi-dimensional multiple variables. It can be large even though the total degree isn't too big and then it's polomial time. But in general the problem with uh large large degrees runs into similar issues and no no efficient algorithm is known for the general case but a pseudopolomial algorithm is known.

23:43 So, um, but this is this is just an aside. We haven't talked about this and u I'm not going to present the algorithm.