Video 5-2: para-NP

0:04 We've defined reductions. The next bit is to define hard problems or complete problems for a certain class. That's how we went from polomial time reductions to the notion of NP hardness and NP completeness. Uh which gave you this strong statement right the one for all all for one. uh either this this single problem has a polinomial time algorithm uh or all of NP does doesn't have um and uh so we'll we'll try to do the same thing for these parameterized reductions.

0:48 So we need an analog of of NP. We know or intuitively FPT is playing the role of P the uh efficiently solvable algorithms in a parameterized sense. Uh but we need the uh kind of supererset of of things that we cannot really solve efficiently but uh we have to somehow have a universe of problems to talk about. And that's not as obvious um what to pick here. But one one choice could be this class that's been called par NP. So parameterized NP. I think it's a natural definition. You uh say we we still allow FPT algorithms. And remember when we went from P to NP we said instead of polomial time we now allow non-deterministic polomial time where we allowed the machine this magic guessing uh operation where it could essentially uh with divine insights take the right of uh two paths without knowing which one it is. formally defined in touring machines as there's many possible computations and if any one of them uh leads to an accepting computation accepting configuration the overall uh input is accepted even if there's one out of exponentially many. So the same we can do here. We allow a non-deterministic machine, a non-er non-deterministic Turing machine, but we allow it an FPT number of steps, right? So same same as before. Uh that's some function of the parameter that's arbitrary and then uh a polomial in the input size. Same notion as before. Uh indeed this class has a few uh promising properties. Um I'm not going to prove those. You'll see soon why. Uh first of all, it's closed under FPT reductions. What's that supposed to mean? Well, um if I have a problem and I can reduce the problem. So say some problem A is in par NP and uh I can reduce some other problem to this problem A then I know B is also in par and P. Um another nice consequence is uh FPT is equal to par NP which again we shouldn't think is a likely thing right this means I can use the full power of non-determinism in an FPT algorithm and that doesn't allow me to do more than doing it deterministically without any guessing. Uh but the two are the same if and only if P and NP are the same. So it's kind of a a strong strong way of saying if I uh have problems in there unless P is equal to NP I won't won't have an FPT algorithm. Uh and you can also prove something uh similar to a kernelization for this class. So you can again transform this this general FPT uh time into a pre-processing step and then a pol um something that's just bounded in terms of the parameter and because the the class is so analogous to NP we can also define hardness in the same way we can say uh a parameterized problem is par NP hard if every other problem in parp can be FPT reduced to it. Exactly the same as we defined NP hard. Every problem in NP can be polomial time reduced to that problem. Then that problem is NP hard. Uh so same same thing here except that we have to carry through uh the parameterizations and use FPT reductions. So we should be happy because that sounds like a a nice theory. It has all the good properties we would want of a complexity class.

4:57 Um, and it seems to nicely play with PNNP. Now, the problem is that it actually plays too nicely with P andnP. And uh let's let's prove this theorem and then uh I'll give you the interpretation afterwards because the proof nicely shows the absurdity of um of par and P completeness.

5:25 So formally the statement is as follows. We have some some uh non-trivial parameterized problem. Non-trivial just means it's not everything a yes and or everything a no instance. That's all all that means. Um so some parameterized uh problem that is par np complete uh then indeed the restriction of that problem to um bounding the parameter by some constant uh is np hard already. I guess this is a bit sloppy. Uh there exists a constant d so that uh the restriction is is already np hard. Uh let's see why that why that might be the case.

6:16 so I got to work with what we have right. So let uh this L and kappa be and par NP hard or par NP complete we need it to be well it is par NP complete so let's not worry about it and let further some other language uh let L prime be nplete So we have to somehow connect these two. So we'll define a boring parameterization kappa 1 that just outputs one for every input. It's the constant uh parameter. Well, uh if L prime is NP complete, that means L prime and kappa 1 is in par NP. Why? Well, we have to show that there's a nondeterministic FPT algorithm for this parameterized problem.

7:52 non-deterministic because the problem is in NP there is a non-deterministic algorithm to decide it in polomial time and that same algorithm is also FPT time because FPT includes uh polomial time and we actually don't need the parameter to be anything it can be one that's what it says here to use kappa one so the same algorithm is also a nondeterministic fpt algorithm for this uh parameterized problem L prime kapa on right now we use that we have a par NP complete problem. So there has to be a reduction from this problem to L kappa No, which means there's some algorithm um I haven't used the name for this. So there exists an algorithm a uh just going from the definition of FPT reduction. So X is in L prime if and only if A of X is in L. That's the uh equivalence. And the running time the running time of a has to be ft in the input.

9:55 So it's f of kappa 1 of x for some function x and n to the c or say size of x to the c for some constant c. But really this means just a constant factor because kapa one is always one right. So whatever f does it can only be some number. Uh yeah I was a bit ambitious with the space here I think. So this is actually a polomial in the size of the length of x. Well that's that's essentially it right. Um so okay this this internal here is one that means f of one is some constant let me use my uh my new page now that I've made it anyways So the running time of a is is actually polomial in x. And um that also means we uh so we also have an algorithm B for our uh parameterized problem here. Let's put that here. So because L kappa is in par time some function FP prime of K * N to the C N to the D whatever let's say C prime now we're just chaining these two things together okay Um we take an in we can take an input for L prime we map it via A to the problem L and then we take this FPT algorithm B to solve it. So if I take B and apply it to the output for A, this decides L uh sorry L prime.

13:15 Sorry, that part is is useless because that's a nondeterministic algorithm. Forget about it. I don't think we need that. Uh the thing is that we we reduce this um MP hard problem to a slice of L where the parameter is bounded by a constant. And so a a prime to a language l lesser or equal d where uh d is just f of one. That's exactly our uh our unknown constant but it's given by f of one some constant that's the uh set of all um inputs in L where the parameter is bounded by this this constant. So L transforms this NP hard language to this language and it's a polomial time reduction because it's running time is polomial in the input size.

14:41 Right? So what we've actually shown is that L prime polomial time reduces to L less or equal D. And that was an NP hard language. So also this one is um it's NP hard. Ah okay. I'm going to try to write it a bit clearer. And that's all we wanted to show. And uh this part is correct but useless. Sorry for the confusion. Right. So, uh we've shown whenever a problem is par NP complete uh already the restriction of the problem where the parameter is constant has to be np hard. So, uh what this means is that really uh almost no interesting problems are parplete. They cannot be in particular. All of these uh cannot be par and p complete because if you bound the parameter by a constant the resulting running time is polomial. Remember uh for each of these problems a trivial solution is to go through all subsets of size k that's an n to the k algorithm is not polomial.

16:08 It's not ft. But if k is a constant then it's polomial. That's the important distinction between FPT and uh what's also sometimes called XP. So uh these um the problems where if you bound the parameter by a constant then the resulting running time is polomial. Um these are much weaker guarantees than FPT.

16:48 Okay. Uh, I'm not officially introducing XP. Uh, but that's these problems. So, you could say it's N to the order K. Uh, or even even worse, I guess. Uh, but that's that's what the running time for these is.

17:21 So this notion is is much too strict and um it won't help us uh for the interesting questions here. So problems where there there's some hope to get a good algorithm but it doesn't seem to work with an FPT time. um it doesn't help us tell why that is the case, why these problems u don't really seem to allow an FPT algorithm. So we'll have to brush up the theory a bit um to make that distinction. Um there are problems that are parplete. For example, graph coloring whether the parameterized PP P graph coloring is par NP complete. But that's virtually just the case because also three coloring where the parameter is three is already NP hard. Okay.