Lecture 04 : Part B

[Music] [Music] okay so that's the definition of NP uh this was essentially given by cook and lemen independently inspired by these optimization problems which are which seem hard but yet when a solution is given it's easy to verify so um yeah so such problems are called in NP or NP collects all those problems for which there is a poly time turing machine M which uh given this certificate you can check whether use the correct answer or not okay so let me mention here that this m is called the the verifier that's the verifier and this U is the certificate for X so verifier and certificate and uh this blue up is polinomial okay so if you look at the length of U it's not much bigger than the length of input X these are the import key points of the definition so let's do an example so in the in problem two which was uh subset sum subset is the certificate right you are given T and what is the certificate of T it's a certificate uh subset whose uh sum is T So this L that we talked about in the definition this corresponding L is s comma T yeah such that s has subset of some T so on input s comma t What will the verifier do the verifier basically guesses this uh certificate so certificate U is uh the subset of s of some t and verifier m is is the touring machine that given St so given s and t and the subset U checks whether checks uh whether U is a subset of s and sigma U is equal to T that's all okay so verifier m is Trivial it just just checks whether U is a subset and whether the elements of U sum up to T and hence by the definition it means that L is in NP you can check this thing the other conditions also you can check that uh the size of U is smaller than the size of s comma T right obviously because s was in the input and U is a subset so it's size is upper bounded so there's no size blow up in the certificate and M is polytime so overall what you get is uh by the definition you get that L this L is in NP and similarly with 1 and three okay so all these uh problems decision problems they are in NP by the definition because we have shown both certificate existence and uh verifier now note that if the certificate doesn't exist it's a no string right so this definition doesn't talk about no strings uh well or I mean it talks about in this way it's an if and only if condition so if X is not in L then there should not be a certificate okay but that is clear so that's the part which you will generally not care about but when X is in L uh the important thing is that there is a certificate easy to verify yeah so now let's Place NP so where is NP so the first claim is that P is contained in NP and second will be that NP is contained in X okay that's the placement okay NP sandwich between p and x uh easy part is that P is contained in NP any problem that's efficiently solvable also has a certificate and verifier right the the solver of the problem is itself also a verifier so that's a trivial part slightly more non-trivial is uh why is NP NEX there the there also the idea is simple you just have you just search for the certificate in the whole Space okay and just count the measure the size of the search space it'll be exponential so let's prove the first part so say l is in P so it is decided by polytime turing [Music] machine M so then for all X for all input x x is in L if and only if MX is 1 right so a string is a yes string if only if this particular solver this efficient algorithm M accepts it right this is by the definition of m so uh what's the certificate here you can take the certificate u in which was in the definition of NP that certificate you can take as the M Mt string okay the verifier M think of M as a verifier with mt certificate so with u equal to with mt m can be seen as a verifier which means that L is in NP okay so this is the trivial part p is in P is In N every L which is in P is also in NP this means that P is a subset of NP it's a sub complexity class if if you will of NP that's the easy part now but NP may also have hard problems right problems which are much harder than polinomial time like this subset sum tsp um integer programming so what is an upper bound on them upper bound are these boot Force algorithms which are in exp so let's now do that part so now say l is in NP with x in L if and only if there is a certificate U and this verifier M some verifier M accepts you right maybe to avoid confusion with the old l and m let's let's call it l Prime and M Prime so take a problem in NP and then for yes strings X there has to be a certificate verifiable by a fast turing machine M Prime which is the verifier in time the time of turing machine M Prime has to be polinomial in N right in N to the D constant d okay so this is what is uh given to you this is the hypothesis that comes from LP Prime being in NP now why is L Prime in X that is what we want to show so we'll look at the Brute Force algorithm what will the Brute Force algorithm do it will try to go over all the use right so go over so searching U takes um 2 ra to n ra to C time right U is a string or of length and is to see uh [Music] so you can search for it this is basically coming from here uh U is in 01 x to the C as U is in 01 next to the C so if you look at the whole Space search in the whole Space there and it's 2 2 N ra to C time and for each choice of you you will run M Prime and check that will take n is to D time so Brute Force algo is 2 ra 2 and ra to C many possibilities of the certificate and uh n ra to D time for each actually what happens is this U is as large as n to the C right so this will take time slightly more time it will take n + n to the C and this thing raised to d right so it takes this much time so first the I mean the certificate blows up slightly then when you run M Prime on that uh I can maybe do it in two steps so the input of M Prime is x and x to the C length and in terms of the input size of M prime it time is raised to D so which you can write on the next page right so that's the time complexity 2 to n to C * n + n to C whole thing raised to D but notice that this is uh still exponential in N it's not more than exponential so this is actually less than 2 to n to C + 1 right you can check this because C and D are absolute constants and N you can take larger so you check this thing this is true and once you have checked this uh this finishes the proof it's an exponential time algorithm it means that L Prime is in D time 2 to N ra2 C + 1 which is clearly X contained in x okay so there that finishes the second part of course this means what this means that uh NP is contained in X okay because we have done this for every language in NP so every problem in P is in NP and every problem in NP is solvable in X okay but X is not good enough this is these are very slow algorithms these are really Brute Force algorithms so that's the open question it's unknown we NP is different from the other two okay so you can ask whe you can ask whether p is uh strictly smaller than NP and you can ask whether NP is strictly smaller than x that's the conjecture which usually we make that NP is strictly between p and X okay not all problems of X can be solved in NP and uh not all problems of NP can be solved in poom time but one interesting thing is that uh these two end points p and X these we will separate in this course okay so later we'll actually be able to show that P polinomial time exponential time are actually different classes so which means that there is a big margin between p and x and um but you don't know whether NP is closer to X closer to P okay those are the open questions so what does n NP stand for this we did not I did not tell you what does NP stand for so NP stands for uh non-determinism so the n in NP stands for non determinism okay so Nonet non-deterministic polinomial time that's what that is what it means so why is it why is such a thing called non-deterministic polinomial time that a better name would have been efficient efficiently verifiable instead of that why this complicated name so this to answer this question we have to define a whole new uh model which is called non-deterministic Turing machines and I think that also you have seen in probably seen in other courses so so we'll shorten this to ndtm non-deterministic touring machines to contrast with Turing machines deter which which we think of as deterministic um so the definition of this will be similar to touring machine except transition function will not be a function um it will be a relation so ndtm is similar to turing machine except that now there are two transition functions so we have alphabet States and two transition functions Delta 0 Delta 1 or you can also think of this as there being a transition relation so what is the difference between transition function and transition relation well in the function U once the configuration is set there is only one way to move to the next configuration in the transition relation with once the configuration is set there might be multiple ways to move to the next configuration there might be multiple next conf configurations that's why it's a relation and in fact it suffices to as you will see later it suffices to just assume there are two options so first option is given by or let me say zeroth option is given by Delta 0o and oneth option is given by Delta 1 okay so function becomes a relation essentially and uh so at any configuration C its transition is no more unique so it has two allowed mve in fact this ndtm has two allowed moves one following Delta 0o and the other Delta 1 okay these are the two moves what now given a configuration at which one of these will the turing machine choose so that we don't we don't see anything about the choice okay the turing machine can take any path there are two paths and we'll only make a statement about what happens in the end of the computation okay so this this is a more fuzzy computational model that's why it's called non-deterministic the the steps are not determined um like we defined in turing machine so ndmm accepts input X if there exists a sequence of choices leading to the except state and output one that we can set as a convention okay so that's the condition we are putting that there should be a sequence of choices so the first Cho Choice say that NTM M makes Delta 0 then Delta 1 then Delta 0 then Delta 1 and so on and reaches the accept state it's HS and outputs one then we say that okay since there is some path uh two acceptance M has accepted X okay so m is not supposed to accept on all the parts Just One path and what is the negation of this the negation is all paths reject then M rejects so if there does not exist such a choice then m is said to reject X and output zero okay so that's the ndtm setting okay there are choices at every step and if a sequence of choices leads to accept then output is one then we say that actually it's a yes string if there is no accepting path then it's a no string and now since we don't talk about uh how the choices will be made this is not really a practical computational model okay this is really this is as theoretical as it gets it's not a practical one turing machine is like computers but this is not like computers so what's the definition of time so time taken by m on X is the maximum number of steps by m to Halt on X okay so this is a bit uh uh sensitive to the to the steps I mean you we are looking for we going over all the accepting paths and what is the longest okay that defines the the time complexity of ndtm so this maximum is over oh this is not just accepting paths sorry these are all paths so what how much time will it take to hold because remember if x is a no string then you have to go over all the paths and see that all of them are rejecting so this so actually this is maximum this is why it is maximum over all the paths so max over all possible Parts okay okay and based on this we will um we'll redefine NP next [Music] [Music] [Music] time [Music]