i’m in graph theory and theory of computation this semester so ur kinda pushing the two together in this video lol, although we don’t really talk about NP complete
Im in a CS theory course, and find this topic non intuitive, I mean its not obvious how to come up with this gadget, basically you have to learn it by heart, and after that you can refer to this kind of reduction in other cases.
Sir, if the vertex cover (optimization) problem is np complete, then there must exist an algorithm that can verify that the given solution is valid and minimum in polynomizal time. is it possible? I'm rally confused because some sources say that it is np complete and others say that it is np hard, which one is it?
So actually NP complete means *both* NP hard (any problem in NP can be reduced to it in polynomial time) *and* in NP (meaning it can be verified in polynomial time, as you say). So you are right to say it's NP hard, but a more precise statement is that it's NP complete, since it's also in NP
Can you, please, tell me were the proof is written? I want to cite it. I need exactly this proof, previously I saw different reductions and they do not work for my needs.
hmmmm,,,,, so if X1 represent a vertex, then what does X1 bar represent? is it a negration of a vertex? does it make sense? if X1 BAR is a sepereate vertex, then why do we select that vertex as negation of x1? and in this case , is it safe to assume that a vertex has no more than three edges?
Because this value of the limit allows us to make a correct reduction from the 3SAT problem. If we set k lower than 2c+l, then for not every satisfiable formula the corresponding graph would have a vertex cover of size
i’m in graph theory and theory of computation this semester so ur kinda pushing the two together in this video lol, although we don’t really talk about NP complete
Thank you so much man! This is the only good explanation out there
Im in a CS theory course, and find this topic non intuitive, I mean its not obvious how to come up with this gadget, basically you have to learn it by heart, and after that you can refer to this kind of reduction in other cases.
Thank you this explanation was a life saver 😪🙏
Thank you so much!!!! This was really helpful!!!
Sir, if the vertex cover (optimization) problem is np complete, then there must exist an algorithm that can verify that the given solution is valid and minimum in polynomizal time. is it possible? I'm rally confused because some sources say that it is np complete and others say that it is np hard, which one is it?
So actually NP complete means *both* NP hard (any problem in NP can be reduced to it in polynomial time) *and* in NP (meaning it can be verified in polynomial time, as you say). So you are right to say it's NP hard, but a more precise statement is that it's NP complete, since it's also in NP
hey thanks for your effort hope you have wonderful life
Can you, please, tell me were the proof is written? I want to cite it. I need exactly this proof, previously I saw different reductions and they do not work for my needs.
1.1 is in a 1007438183 using 32
hmmmm,,,,, so if X1 represent a vertex, then what does X1 bar represent? is it a negration of a vertex? does it make sense? if X1 BAR is a sepereate vertex, then why do we select that vertex as negation of x1? and in this case , is it safe to assume that a vertex has no more than three edges?
X1' or X1 Bar is a negation of X1
Thank you for the video :)
thank u so much!
Semi-related to this, do you plan on doing anything in computability theory too?
I didn't see this until just now! Yes, eventually. I want to do some Kolmogorov complexity, as well as some decidability of theories and such.
@@EasyTheory That would be awesome! Especially Kolmogorov complexity as I find that to be one of the most interesting areas of CS/information theory.
Vertices allowed = 2c + l is unclear to me.
Why is this the limit?
++
Because this value of the limit allows us to make a correct reduction from the 3SAT problem. If we set k lower than 2c+l, then for not every satisfiable formula the corresponding graph would have a vertex cover of size
far-fetched explanation