Video 3-3: Strong NP-hardness

0:03 Nonetheless, in this first subsection, let's talk about the corresponding hardness uh theory and that's strong NP hardness. Uh the definition is simply a problem is not only NP hard but strongly NP hard if there is a polomial so that this value restricted subpro is still NP hard. So even if you restrict um max int to a polomial the problem remains np hard and then obviously a pseudo polomial algorithm wouldn't help because um there uh you remain with an np hard problem so it um it's unlikely to exist. Okay.

0:53 Um let's uh let's briefly uh try to prove this. Um if P is not NP and you strongly NP hard then there cannot be a pseudo polomial time Uh this means there exists a polomial P. So that this value P U problem is NP hard. That's just the definition from above. So assume towards a contradiction that a was a pseudo polomial u. Well that means that a runs in time a polomial in uh another polomial an and max int if x is from the from this value pu then I can further bound this by P of X or P of N. And so the whole thing is a polomial for some constancy But that means I'm uh computing the solution for all instances of an empty heart problem in polomial time. So I would have shown that value p of u is in p uh but we assume it's np heart. So that would mean p is equal to np. That's a contradiction to our assumption.

3:31 that uh P is not equal NP. So the assumption must have been false and there cannot be a pseudo polomial time algorithm. Okay. Didn't need the extra space after all.

3:56 And as a last example, let's show that indeed one problem we know of is strongly hard. And I'll leave it with a very simple picture proof.

4:09 Um we show [Music] that the um Hamiltonian cycle or Hamiltonian path problem cycle is more direct reduces to uh the TS sorry the value restricted problem of TSP where I restrict the values to be two at most. And so what's the input for uh for a Hamiltonian cycle? It's a graph.

4:50 Oopsie. And the question is, is there some Hamiltonian cycle in this path in this graph? Now I'm just going to give uh the transformation just assigns distance one to each of these edges in the graph and distance two to all the non- edges those that don't exist. So uh there's a lot of non- edges to draw. Uh I'm not going to do all of them. But the point is if uh this is certainly an input restricted problem, all the integers that occur are one or two. And so um if I can find a path in this uh a round trip in this graph of cost exactly n then that is a Hamiltonian path and vice versa.

5:45 Okay. Still dashed lines. Come on. cycle right so this is one example it's a very simple reduction it's the same reduction that people may have used for showing tsp is hard and in in this case it just produces only instances with tiny uh numbers Um I'm I'm probably okay I'll skip the proof this because we're running of this running out of time. A tiny remark that's sometimes useful. You can think of strongly MP hard also as um it's still MP hard if you force the encoding for the integers to use the unary encoding. What's unary encoding? Well, the numbers 10 would be represented by 10 1's. Okay, so you blow up your input size which is the same which effectively transforms the input size into max int or a polomial of max int. And you can show that this is uh equivalent uh a problem is strongly np hard if and only if the encoding for that problem with unity encoding for all integers is np hard. Sometimes that's more convenient to show or more convenient to reason about good. Uh so that's that's all on pseudo polomial algorithms. If the numbers are indeed small this is often good enough.

7:47 um is a fairly restricted technique though indeed the examples I listed on the slides are the only ones I know I'm not sure if there's a a second fundamentally different problem where pseudo polomial algorithms would work and so we'll have to work a bit harder in the coming weeks to extend