Have you ever played the game Flow or NumberLink? This video does a deep dive into the world of the Flow puzzle by taking a brief look at its history, then exploring its place in the world of complexity theory.

This video is dedicated to ML for playing the game alongside me and listening to me explaining the research that went into this video. It is also dedicated to GS and JH for always entertaining me in discussing the random puzzles/problems I come up with. Lastly, this video is dedicated to RG for inspiring passion in me and encouraging me to continue my journey of teaching.

I also would like to address a couple of questions that you may come up with while watching the video:

Q: You said that we should consider an arbitrary 3SAT formula, but then proceeded to use a specific 3SAT formula.

A: Good point. Choosing a specific 3SAT formula was solely done for the purpose of visualization. However, the procedure of constructing the graph is generalizable because it works for any 3SAT formula (create vertices for each variable, each clause, etc.)


Q: I'm confused as to what the difference is between P and NP. The "friends subset" question doesn't seem that hard since we used brute force. Didn't we essentially use brute force for the "oldest person" question?

A: Yes! Both are essentially brute force. The difference appears in the amount of "queries" you have to do. For the "oldest person" question, you need to query every person exactly once. So if there are n people, then you need to only make n queries. For the "friends subset" question, I would have to query every group of 8 people. There are (n choose 8) = (16 choose 8) = 12870 such groupings. The second problem requires many more queries and grows at a faster rate.

Finally, I would like to thank Grant (3Blue1Brown) and the team that develops manim for the brilliant tool that is manim.

Music Credits:
'Filaments' by Scott Buckley is under a Creative Commons license Attribution 3.0 Unported (CC BY 3.0)
@ScottBuckley
Music promoted by BreakingCopyright: https://bit.ly/filamentssong