What P vs NP is actually about

What if we could run algorithms backwards? We discuss how we could do this by turning algorithms into circuits and encoding those into satisfiability problems. We then explain how it all connects to P vs NP.

#somepi

0:48 Satisfiability
2:15 Breaking RSA
8:46 General reductions to SAT
12:03 P vs NP

Richard Hladík: Script editor, animator
Gabor Hollbeck: Video recording, video editor
Václav Rozhoň: Writer, animator
Václav Volhejn: Narrator, animator, script editor

Thank you to our beta testers: Matěj, Honza, Filip

Music: Thannoid by Blue Dot Sessions
Pictures: Intel 8008 from Ken Shirrif's Twitter, others from Wikipedia, Internet

[SpriteGuard]

The wildest part of P vs NP to me is just how many dead ends there have been. There's an entire genre of theorems ruling out particular ways that it might be solved, because it's far easier to prove that a line of reasoning will never resolve the issue than it is to actually solve it.

[SpektralJo]

Remember, even if P=NP, that doesnt mean that the SAT solver algorithm is fast on a practical level. Multiplication is in O(n log n), but that algorithm hast constants that don't fit into the observable universe. Cryptography is only doomed if we find a practically "fast" algorithm

[jdave]

This is a really good explanation! P = NP never made a satisfyingly amount of sense to me, but this helped bridge that gap a bit! Thinking of it as “can we run solvers backwards?” is a cool approach! Quite sensible!

[darrennew]

Very cool. I have a PhD in computer science and I never heard PvNP explained so elegantly.

[chamidumadumal]

Congrats on winnig the Summer of Math Exposition this year. Great Job!

[Ganerrr]

Hands down best explanation on why NP problems are equivalent

[NovemberIGSnow]

I had a fun conversation with a coworker once who suggested that it may be possible to prove that it's impossible to prove or disprove P=NP. I noticed a fun contradiction there. If you can prove it's impossible to show P=NP or not, then there is no Turing machine that can solve an NP-complete problem in polynomial time, because the existence of such a machine would prove the algorithm.

My coworker countered with the notion that there could be a TM that seems to solve NP-complete problems in polynomial time for all inputs we've given it so far, but that we might not be able to t prove its complexity does not eventually get dominated by a non-polynomial term for sufficiently large input.

I countered with the idea that you could analyze the runtime of the TM with a TM to find if there's a sufficiently large input where the algorithm becomes dominated by a non-polynomial term.

He said that's the halting problem.

Oops, lol. He was right.

[rileyn]

This is the best explanation I've seen on why NP contains all the problems with easily verifiable solutions. I've always known that but didn't quite get why until now. Great video. You definitely deserve more subscribers

[skorp]

I really appreciate the Stuff Made Here attitude to background screens xD
Amazing as always. I've heard lectures on satisfiability (esp. classes of SAT-solvers and reduction) and mathematical logic and this was a great overview as well as an interesting perspective on the content. Thank you for your work! :)

[DemonixTB]

important to note that P is still a very large space
is still in P, while O(2^0.01*n) isn't
from that far away, many problems look the same, it is much more useful to prove a specific algorithm is O(n log n) and that the constants aren't too big, than it is to prove P=NP if the reductions require an incredibly unwieldy degree polynomial
(even better to find easily parallelizable algorithms that are just a bit higher on the complexity side, since the takeover point for the given assymptotic functions can land outside of general human interests or dataset sizes)

[mattbatwings]

Huge congrats on winning somepi :)
- number 2

[cambrown]

To the point of the great analogy you made regarding entropy and the 2nd law of thermo: in the case of computers, it quite literally is a matter of entropy. In a simple two-input digital gate (i.e. AND, OR, NOT, XOR, etc.) we take two bits of information and reduce it to a less organized state, being a single bit of output and heat! I have a feeling that current digital computing is limited by its paradigm to find a solution this problem. Loved the video, had never made these broader connections between the hardware world and theoretical CS. Signed, a junior CPU designer.

[tjaron]

I probably would have needed such a video back in my computational complexity class. You did a good job at explaining the P-NP-Problem!

[harriehausenman]

Great fresh take on the topic. Fantastic video with amazing production value! Thanks a bunch 🤗

[jmarvins]

interestingly enough, eminent computer scientist donald knuth was a contrarian on the P vs NP issue, and thought that P probably does equal NP

his reasoning was heuristic: only the tiniest portion of the infinitely many possible recursive functions will ever be knowable to us - let alone practical to use - due to the nature of infinity, and thus the fact that it doesn't seem impossible should make us suspect there might be some inconceivably large P-class SAT-solving algorithm out there beyond Graham's Number or whatever other huge finite number of your choice

i am not sure myself that this is a convincing argument, but nobody has proof and Knuth certainly had a better intuition about things than most, including me...

[EHuelsz]

Excellent video, I have been following closely videos released here on Youtube related to P vs NP for the last 13 years and, in my opinion, this is the one that best explains the core of NP-completeness definition, thank you very much.

[michal]

This reminds me of good old days when I wrote my MSc on SAT. My intention was to solve this fascinating problem but it turned out really damn hard so I ended up rediscovering some wheels and playing with satisfiability solvers and SAT encodings of various computational problems.

[MishaBehersky]

bro used subway surfers trick while explaining 10:35

[bryanredd]

This is by far the best explanation of P=NP I have ever heard. Great work!

[programmer]

Excellent use of visuals to simplify the explanations !!