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

Показать описание

Here we give the full proof that SAT is NP-complete, which is a general polynomial-time reduction from any problem B in NP. We use the "tableau" proof which encodes the transitions of a nondeterministic poly-time TM.

▶SEND ME THEORY QUESTIONS◀

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

Рекомендации по теме

Комментарии

i passed my exam thanks to you, thank you!! great job

leksndr

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!

charlesrodriguez

Thanks for the clear explanation! Made me understand everything I didn't during the lectures.

MaxGelm

Now that is a mind blow. 💥8|
We just went over it a few days ago in Discrete 2. Talk about crazy.

KnakuanaRka

You are the curriculum... appreciate you so much man

chretienli

for anyone getting this in their recommended, SAT stands for Boolean Satisfiability Problem

jemesmemes

You're the best . Thank you so much

hoanguyentrong

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?

YoussefKossale

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)

BjarkeEbert

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?

sheikhshakilakhtar

Could somebody explain why the columns of # at the start and end are necessary?

KnakuanaRka

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

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

NP-Complete Explained (Cook-Levin Theorem)

16. Cook-Levin Theorem

Cook Levin Theorem - Intro to Theoretical Computer Science

The Cook-Levin Theorem (part I)

COOK'S THEOREM

Cook Levin - Georgia Tech - Computability, Complexity, Theory: Complexity

Cook's theorem | NP Complete Problem

CSE104, Lec 5: The proof of the Cook-Levin theorem and the NP-completeness of 3SAT

COOK LEVIN THEOREM

ToC NP completeness and Cook Levin theorem 2 Circuit SAT

Algorithms for NP-Hard Problems (Section 22.2: 3-SAT and the Cook-Levin Theorem)

8. NP-Hard and NP-Complete Problems

The Satisfiability Problem, and SAT is in NP

Prove and Explain Cook Levin Theorem

Proving P=NP Requires Concepts We Don't Have | Richard Karp and Lex Fridman

ToC NP completeness and Cook Levin theorem 3 3SAT

mod02lec08 - Cook Levin Theorem: Part 2

Question regarding Cook-Levin theorem proof

mod02lec07 - Cook Levin Theorem: Part 1

Computer Science: Cook-Levin theorem proof's requirement of $phi_{cell}$ (2 Solutions!!)

Cook Levin Summary - Georgia Tech - Computability, Complexity, Theory: Complexity

Lecture 06 : Part A - Cook-Levin Theorem

ToC NP completeness and Cook Levin theorem 1 Introduction and Preliminaries