NP-Complete Explained (Cook-Levin Theorem)

[@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.

[@dekrain]

What about the 'states' of Turing machines?

[@TejaKarlapudi]

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

[@kutilkol]

lol. love that comment. so much agree

[@ben_jammin242]

Teja, from what I understand, the idea of "reduction" is a bit of a loaded term but in this context I think the aim is to "simplify" a problem into fundamental computational units of some variety (such as logic gates, variables as arguments etc) such that two seemingly different problems can be equated. if you can reduce them to the same elements, then they can be solved in the same way. alternatively, if you're able to successfully solve one, then the rest should be easier to solve. Undefined, I feel like I may be missing something here!

[@adityaprasad465]

Something something heart something?

[@saidalas7763]

this was a bs video , plagiarism like most of yt explanotry vids

[@darsek285]

@@adityaprasad465 XDDDD

[@cademade4195]

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

[@maxschmidt666]

Ahhh this feels like Math in school: First 5 mins: Too ez. Afterwards: I will join Patrick Star unter his rock

[@charlesrosenbauer3135]

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.

[@John-lf3xf]

Charles Rosenbauer Yeet boiii

[@purnimapotukuchi9748]

Nice comment. Didn’t know that!

[@ojasdamankar9851]

That's why they why theoretically it's pessimistic as in real world it could work at times. But no guarantee

[@TheRooster1337]

Hmm let me look up what a NP-Complete is... oh a problem that is in NP! Very helpful, thanks a lot.

[@KeepingUp_withAI]

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

[@하루과학]

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

[@thisis2ne1]

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

[@ejsafara456]

hello thank you for this video, you have made me understand the gibberish of my profesor now i actually understand what s going on

[@edwardwong654]

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

[@davidmarquette9268]

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.

[@nytr]

The only gate you need is Nand

[@tomerwolberg37]

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

[@DoktoreBlah]

The heart circuit actually represents every possible state the turing machine can go into. That makes it possible to check if the problem is solvable which is the case when the resulting circuit (or in case of SAT: the resulting formula) is satisfiable.

[@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?

[@Mexximillion]

I didn't get it either, I thought Turing machines can move as far as their inner state dictates them considering the last read input.

[@nidhalabida869]

This channel is the 3blue1brown of computer science

[@Nwolf1840]

wut?

[@nirpaz677]

finally another upload!!!

[@shuangli5466]

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

[@SKyrim190]

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!

[@DrRiq]

I very much agree with this. Stop it with the goofy animations, they're not funny and if anything are distracting. The main takeaway from these videos is how you guys explain things step-by-step, not the references to geekdom.

[@dmitryr9613]

Personally I disagree, it helped me stay focused on the explanations because the concepts are difficult and trying to get through them when you are below a 80% understanding of what is going in is a struggle and a slug fest. So the stupid items popping up forced my brain to pay attention

[@xianggu9425]

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?

[@ZombieBestOfficial]

np for the question

[@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

[@NikitaJain123]

Are the heart circuits supposed to represent 3-SAT?

[@bapple7844]

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

[@Watermeba]

You are a god. i should have came here first

[@sampugh6404]

Amazing video. Thank you.

[@stevepoper8073]

He got me with the cells at 5:02

[@stevegerben]

Pumped to watch!

[@fit_with_a_techie]

why do we have used only one not and and gate??? is there a significance of 3 inputs? if we want 1 as an output when all input variables are assigned as 1 than why have we not used AND gate simply? please reply!!!

[@welcomeaioverlords]

Very nice!

[@orbitmarketing-usa]

Great stuff!

[@masbro1901]

question. How do we program the turing machine, the machine follows set of rules that we defined. where and how to program that? many thanks.

[@anandsuralkar2947]

u need to learn theory of computing for that i guess. its just like the PDA or DFA. just it has way to write on tape and move in both directions.

[@anandsuralkar2947]

u can make turing machine by drawing the state diagram idk if u mean program turing machine in practical way like a code?

[@masbro1901]

@@anandsuralkar2947 yes, you explain the "how" part, but not the "where" part, you said "it has way to write..." thats what i'm asking, and yes program turing machine analogy with practical way like a code. we know how code in modern machine by translate to binary, but how in turing machine?

[@nlysts]

Great channel very informative

[@swordwaker7749]

Wait, protein structure prediction is not NP-complete. If it was, we would be developing protein computer now.

[@Mu_Lambda_Theta]

Hmm. Sure, it would be cool having a machine do the heavy lifting, but there would probably be some problem, like efficiency. Nevertheless, this is an interesting possibility, to make the laws of physics solve everything. Like a Quantum computer. Actually, a quantum computer would be a protein computer, as protein folding is just all of the atoms and their electrons interacting with each other, i.e. protein folding is a more specialized version of quantum problems. So, in a way, protein computers ARE being built.

[@secnytsecnyt2981]

Can you prove that protein structure prediction is not NP-Complete?

[@ridwanulhasantanvir6456]

0:30 NP complete

[@broccoloodle]

Dear, there might be a bug in your explanation. The construction of the heart circuit is not only dependent on the symbols as shown in the video. It should be a combination of both symbols and states. Thanks

[@ErezWeiss0]

Just brilliant! Thank you so much

[@crustyMilk]

lolz wasnt expecting a bonfire. Praise the sun.

[@water594]

That problem with the gates seems easy though. Just reverse it. First tealising that the NOT gate flips it to the necessary 1 for the AND to function so you can reject all the 1s in the top like of the input data, then realising that a 1 in either of the OR gate inputs will output a 1 thus meaning you only need to check one. That makes it visually easy but to make it somewhat easier to code you could convert the imput number into a binary number and then filter them by 2 if statements. IF n>=100 reject. IF n=000 reject. IF ELSE n wil produce a 1. Or you could convert the 3D series of inputs into a 2D line and instruct a reader to read with the rules; algorithm 1: IF 1 output 0 and move 3 right and initate algorithm 1, IF 0 move 1 right and initiate algorithm 2 algorithm 2: IF 1 output 1 and move 2 right and initiate algorithm 1, IF 0 and move 1 right and initiate algorithm 3 algorithm 3: IF 1 output 1 and move 1 right and initiate algorithm 1, IF 0 output a 0 and move 1 right and initiate algorithm 1 This would generate a new string which you could use to check whether it outputs a 1 or 0. I guess thats still exponential tho because every new term takes you a maximum of 3 extra steps. Not saying I solved P = NP or anything just brain go brrrr and make a solution.

[@imaansayed8147]

If something that's known to be hard seems easy, it just means something's missing :P

[@water594]

@@imaansayed8147 I made this comment 10 months ago and have no recollection of what this was even about to be quite honest.

[@imadvurkadinohinto]

Wow this is awesome

[@LFSPharaoh]

The “head” at 5:24 is from halo isn’t it

[@welldang4]

totally guilty spark, right?

[@furkanberk8176]

How can i do animation like this?

[@kl191]

I love your v ideos and the animations used

[@EpicSwag3345]

Top class!

[@rpCricketLove]

Amazing 👍

[@NathanTheNinjaTaylor]

Didn't expect the Gurren Lagann drill lol

[@petros_adamopoulos]

NP-Heart problems, I get it.

[@danielkrajnik3817]

how your videos circumvent copyright law is at least an NP-hard problem

[@tonymartinez5798]

….. what?

[@pkavenger9990]

we need gohan to eleminate cell.

[@StevenAkinyemi]

P = NP if you have a time machine. In fact all problem are instantaneously solved. There is no concept of complexity at that point. Complexity is a problem of time which is also a problem of state. You can simply jump to a state where the answer is solved. Since there are infinitely many states with infinitely different morphisms, all problems are solved.

[@John-lf3xf]

Analytic reduction to show that the problems are the same.

[@borisalmonacid]

Metaheuristics next video please :D

[@valeriyv1073]

I understood nothing. Funny pictures are emphasizing surrealism of the topic

[@mpamizoemmanuel6474]

What ?

[@hyunwookjung9231]

Too much unnecessary visual effects for a confusing concept

[@sagerenstrom-richards842]

t h a n k y o u

[@quispeachahuanco826]

Nice!!

[@ME6803]

Hey, your depiction of the input tape in the Turing machine is wrong, it's supposed to be infinite on both sides according to the standard definition.

[@charlesrosenbauer3135]

I think the point was that this is a Turing machine specifically to solve an NP problem. NP problems won't have an infinite size, and as a result will place bounds on the size of the tape. Sure, the tape still can be infinite, but the point was that the rest of the tape doesn't matter because the problem is bounded.

[@f_f_f_8142]

Onesided and twosided Turing machines are easily convertible. Even the number of tapes does not matter if you do not differentiate between polynomial running times.

[@god.hand.]

ceil hahahah. what about 17(Android 17).

[@HosseinOutward]

wut

[@chriskh93]

Yo mo5eef

[@CaptainGibbons]

The pop culture references seem forced and almost condescending.

[@abhay8437]

I see pokemon, I click

[@devianbomb]

m3m3z

[@jaerdelight3551]

чё он несёт?

[@koblaise]

cool

[@13enyamin79]

use it as a dislike button

[@abdulbasit0123]

Bs

[@martininorway4113]

Really bad explanation. I don't think so you understand NP, NP-Hard, NP-Complete terms properly

[@loookclick938]

The fuck?