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!
