The link you provided is the proof of the Cook's theorem, but could you please share the link of the generic proof of reducing SAT to 3-SAT in polynomial time? Thanks!
So to prove 3SAT is in NP we reduce SAT to 3SAT. What if we want to prove that SAT is in NP? as far as I know every problem in NP can be reduced to the other problems. What about the first problem prove? Its like the chicken first or the egg + which one is the chicken and which one is the egg? Thanks for the great video!
Of course! Here is a link to a more easily digestible proof of Cook's Theorem: www.cs.otago.ac.nz/cosc341/proof_Cooks.pdf The actual theorem and proof involves a bit more complexity theory and automata theory than we cover in this course, but the rough idea is to convert every possible problem into a Boolean statement, which should be possible since each problem is a mathematical statement!
Best explanation ever. I'm studying for my exams right now and this is the best help I could get on UA-cam.
You are cool. Thank you. Stuck on your video and very glad i found your explanation.
Love you and greetings from Romania
So much clearer now, thank you so much!!
U saved me before my exam. Thks a lot.
The link you provided is the proof of the Cook's theorem, but could you please share the link of the generic proof of reducing SAT to 3-SAT in polynomial time? Thanks!
thank you for the explanation! is it possible to get these lecture notes?
Thanks for these wonderful lectures. Also can you share your notes.
At 14:42, couldnt you just substitute the terms Xa represents into the formula to get 3-CNF?
when i plug this into a truth table, the answers are not the same. is there a reason why it would be wrong?
you made a mistake
is it not a rule that in a clause we cant have 2 literals the same as here XA is same for last two clauses
So to prove 3SAT is in NP we reduce SAT to 3SAT. What if we want to prove that SAT is in NP? as far as I know every problem in NP can be reduced to the other problems. What about the first problem prove? Its like the chicken first or the egg + which one is the chicken and which one is the egg?
Thanks for the great video!
To show that SAT is in NP is easy since we can just plug our variable assignment into the truth statement!
1:27-2:00 Conjuctive Normal form
Can you link the proof you mentioned in the video?
Of course! Here is a link to a more easily digestible proof of Cook's Theorem: www.cs.otago.ac.nz/cosc341/proof_Cooks.pdf
The actual theorem and proof involves a bit more complexity theory and automata theory than we cover in this course, but the rough idea is to convert every possible problem into a Boolean statement, which should be possible since each problem is a mathematical statement!