Cook-Levin Theorem: Full Proof (SAT is NP-complete)

  Рет қаралды 20,925

Easy Theory

Easy Theory

Күн бұрын

Пікірлер: 26
@SaadathMeerapuram
@SaadathMeerapuram 14 сағат бұрын
I have been trying to read my prof's slides for hours now and understood nothing. I watched this one video of your and I understood everything. Thank you sir 👍
@4leks4ndr47
@4leks4ndr47 Жыл бұрын
i passed my exam thanks to you, thank you!! great job
@charlesrodriguez6276
@charlesrodriguez6276 3 жыл бұрын
Bro you are literally a life saver. Your explanations are amazing, the content is top-notch, you put a lot of effort into explaining each detail. Will definitely buy the textbook you have coming thank you for this content!
@MaxGelm
@MaxGelm 3 жыл бұрын
Thanks for the clear explanation! Made me understand everything I didn't during the lectures.
@EasyTheory
@EasyTheory 3 жыл бұрын
You're very welcome!
@PriyaSharma-sz1sl
@PriyaSharma-sz1sl Жыл бұрын
Ultimate explanation 💯👌
@jemesmemes9026
@jemesmemes9026 3 жыл бұрын
for anyone getting this in their recommended, SAT stands for Boolean Satisfiability Problem
@EasyTheory
@EasyTheory 3 жыл бұрын
Thanks! I changed the title to reflect that.
@chretienli6405
@chretienli6405 3 жыл бұрын
You are the curriculum... appreciate you so much man
@KnakuanaRka
@KnakuanaRka 3 жыл бұрын
Now that is a mind blow. 💥8| We just went over it a few days ago in Discrete 2. Talk about crazy.
@hoanguyentrong2636
@hoanguyentrong2636 3 жыл бұрын
You're the best . Thank you so much
@EasyTheory
@EasyTheory 3 жыл бұрын
You're very welcome!
@alicianieto2822
@alicianieto2822 2 жыл бұрын
Thanks!
@YoussefKossale
@YoussefKossale 6 ай бұрын
I don't quite understand how we can put NTM configurations one after the other in the table? do we put only a path of configs from the execution tree of the NTM?
@goranivankovic221
@goranivankovic221 5 ай бұрын
We don't actually fill in this table with values, we only encode that they must follow the rules of the given NTM. If all formulas 1,2,3,4 are True, then there exists some path of configs that finishes with q accept. It is maybe like Sudoku. We can solve the sudoku in multiple ways. Once we solve it we can track back for each step and check that rules of sudoku were followed. This formula would be True only if there exists some way of solving the Sudoku, not telling us exactly how to fill it in.
@沈昱宏-e6n
@沈昱宏-e6n Жыл бұрын
ur the best, tks!!
@Giorgio-pv1hj
@Giorgio-pv1hj 3 жыл бұрын
you're great! thanks!
@EasyTheory
@EasyTheory 3 жыл бұрын
No, YOU'RE great!
@BjarkeEbert
@BjarkeEbert 3 жыл бұрын
Thanks for the explanation! Where it clicked for me is that given the input to the Turing machine, there's a known upper bound on the Turing runtime, and thus on the tape, making it a finite problem for THAT input: no infinite tape. Small addition to your explanation around 20 minutes: I guess the important thing is that Phi1..Phi4 can be generated in polynomial TIME, not that the result formula had polynomial SIZE (which follows, btw)
@joesilvester7235
@joesilvester7235 3 жыл бұрын
what is the time complexity for this
@EasyTheory
@EasyTheory 3 жыл бұрын
I'm assuming you mean the reduction, and that will be some polynomial multiplied by the runtime of the original Turing Machine. (The "size" of the formula involves O(n^(2c)) "cells", where n^c was the runtime of the TM.) So the size of the *formula* is a polynomial in the size of the original TM. However, the runtime of *any algorithm for SAT* might not necessarily be polynomial. This is purely the reduction from any NP problem to SAT.
@KnakuanaRka
@KnakuanaRka 3 жыл бұрын
Could somebody explain why the columns of # at the start and end are necessary?
@guyelf9419
@guyelf9419 3 жыл бұрын
I believe it's just a convention to mark the beginning and end of the Turing Machine. When you're running the TM you can't really tell on which cell index you're located and since here we are limited by the size of the table to be of O(n^2k), this is how you know you reached those limits.
@sheikhshakilakhtar6844
@sheikhshakilakhtar6844 3 жыл бұрын
I have a request. While I think I have understood this proof, which is also the one presented in Sipser's book, I am having a hard time trying to understand the one used in the book by Arora and Barak. Would you mind making a video on that and tell us where the two proofs are different and where similar?
@EasyTheory
@EasyTheory 3 жыл бұрын
I'll look and see! I'm guessing the terminology is slightly different but the basic proof strategy is the same.
@sheikhshakilakhtar6844
@sheikhshakilakhtar6844 3 жыл бұрын
@@EasyTheory Thank you
3SAT is NP-complete Proof
17:18
Easy Theory
Рет қаралды 32 М.
The Satisfiability Problem, and SAT is in NP
10:54
Easy Theory
Рет қаралды 53 М.
Savitch's Theorem (Complexity Theory), Statement and Proof
26:04
Hamiltonian Path is NP-Complete (Directed, Reduction from 3SAT)
22:46
16. Cook-Levin Theorem
1:18:27
MIT OpenCourseWare
Рет қаралды 21 М.
What Makes Mario NP-Hard? (Polynomial Reductions)
10:53
Undefined Behavior
Рет қаралды 44 М.
Why There's 'No' Quintic Formula (proof without Galois theory)
45:04
not all wrong
Рет қаралды 547 М.
16. Complexity: P, NP, NP-completeness, Reductions
1:25:25
MIT OpenCourseWare
Рет қаралды 416 М.
What P vs NP is actually about
17:58
Polylog
Рет қаралды 138 М.
Vertex Cover is NP-Complete + Example
19:13
Easy Theory
Рет қаралды 32 М.
8. NP-Hard and NP-Complete Problems
31:53
Abdul Bari
Рет қаралды 2 МЛН