NP-Complete Explained (Cook-Levin Theorem)

What makes a problem "harder" than another problem? How can we say a problem is the hardest in a complexity class? In this video, we provide a proof sketch of the Cook-Levin theorem, introducing a critical concept known as NP-completeness.

Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Justin Chen, Zachary Greenberg, Elaine Chang, Brandon Chen

—

References:

Lectures:

[UndefinedBehavior]

Hi everyone! I can't believe it's been so long since the last video (4 months!)

There's one point I gloss over in the video, hopefully it's not too confusing. I describe circuits as operating on a purely binary language, but around 7:00 while giving an overview of the conversion, I'm showing lots of other characters (like blanks, 1 with a Turing machine head, etc.) as an artifact of how a Turing machine works. In general, we can convert from a multi-character language into strictly binary one, and there are tricks we can do like representing the Turing machine head on the tape itself. You can imagine an intermediate conversion from a more human readable Turing machine to a strictly binary one, before going to the circuit.

[TejaKarlapudi]

I understand that you explained everything very clearly, but I still don't get it.

[cademade]

What I learnt... Understanding np problems is an np problem.

[maxschmidt]

Ahhh this feels like Math in school: First 5 mins: Too ez.

Afterwards: I will join Patrick Star unter his rock

[charlesrosenbauer]

Interestingly, there are actually programs for solving SAT problems called SAT solvers. They still take exponential time, but they are able to locate and exploit many kinds of structure in the problem (real world SAT problems often have a lot of structure to them), allowing them to be solved very quickly. You can easily turn the SAT problem into a graph showing what kinds of constraints exist between different variables, and often times you'll find that these complex SAT problems are actually composed of a large number of much smaller, mostly independent SAT problems.

A modern SAT solver can actually solve some problems with over a million variables in under an hour, though they can still struggle with problems with fewer than a hundred if there's not enough structure to exploit.

There are also SMT solvers, or Satisfiability Modulo Theory solvers, which are basically SAT solvers with higher-level constructs bolted on. That way an arithmetic operation in your NP problem doesn't have to be transformed into hundreds of variables and constraints in the solver, and can often be solved faster with some simple math operations.

[Rivalius]

Thank you for taking the time to make this. Keep up the good work! Subscribed !!

[kergcgb]

You explain the concept of NP-complete problems better than my professor.

[thisisne]

I love this so much, please start making videos again!

[davidmarquette]

damn thanks man, i'm taking a theory of omputation course and struggling to understand the lectures because they speak in such high level terminology. i understand it perfectly from your video so its much appreciated.

[edwardwong]

Uh I am probably going to have to watch this one again....and again. But I like the way it is explained.

[tomerwolberg]

But doesn't the state of the turing machine also affects the output of the heart circuit?

[nidhalabida]

This channel is the 3blue1brown of computer science

[TheOneMaddin]

I dont get your Turing machine model. The head has no state. And how can it be that the next manipulation only depends on the neighboring cells on the band? Can you elaborate?

[SKyrim]

While I appreciate the effort and the information, I think some of the animations are becoming excessive and kind of distracting. Lining up a roll of Sells from Dragon Ball because "Hahaha, cells!" didn't inform me of anything and it is not creative enough to be funny...

I am probably sounding harsher than I meant, but I want your channel to grow, because you tackle on explaining some very hard stuff without hand-waving most of the details, which I totally appreaciate!

[FaKeAdvent]

The machine is an infinitely long tape, broken up into "Cells", which can only defeated by Son Gohan. Nice joke at 5:04 :D

[shuangli]

these video are so good why aren't there more views.

[NikitaJain]

Are the heart circuits supposed to represent 3-SAT?

[Watermeba]

You are a god. i should have came here first

[bapple]

People unfamiliar with dbz are probably very confused by 5:06

[xianggu]

so if I can find a problem, prove it's easy to verify (meaning I can find a polynomial-time algorithm to verify whether a solution is valid or not) AND prove it's not easy to solve (meaning I can prove there does not exist a polynomial-time algorithm to solve this problem). What does this mean? I think this means this problem belongs to a specific complexity class, what is the name of this class?