Complexity Theory Explained Visually | P vs NP

Channel:
Canada Art of the Problem
Subscribers:
175,000
Published on ● Video Link: https://www.youtube.com/watch?v=rK3xcRYLWeg


Duration: 11:16
7,520 views
557

I wasn't satisfied with other P vs NP videos so I came up with a more visual explanation of P vs. NP and specifically the difference between polynomial vs exponential growth by considering where loops occur in an algorithm. This is part of a longer CS series: https://www.youtube.com/watch?v=fjMU-km-Cso&list=PLbg3ZX2pWlgI_ej6ZhGd45-cPoWLZD9pT

This video delves into the fundamental principles that govern the computational universe, influenced by the minds of Von Neumann and Turing.

0:00 - The origins of the universal machine and the Von Neumann architecture
1:00 - Time and Space complexity intro
1:25 - John Nash writes letter to NSA
2:17 - Graphing time complexity
2:49 - Linear time growth
3:16 - Polynomial Growth
4:30 - Exponential Growth
7:34 - NP problems
8:39 - Non deterministic machines
9:12 - Non deterministic polynomial time
9:50 - NP Complete
10:16 - Does P = NP?



Other Videos By Art of the Problem


2024-09-09Reinforcement Learning | A history from Tic-Tac-Toe to Humanoids
2024-09-06How AI Understands Game Positions (Value Functions)
2024-08-15Origin of Reinforcement Learning
2024-07-31The Origin of Reinforcement Learning | How AI Learned to Feel
2024-04-11What Makes Human Intelligence So Special?
2024-04-07Intelligence: A 600 Million Year Story
2024-04-06How Intelligence Evolved | A 600 million year story
2024-01-223 Layers of Learning #evolution #ai #machinelearning #science
2024-01-12How the first neural network learned (backpropogation) #ai #machinelearning
2024-01-09What is a distributed representation? #ai #machinelearning #technology
2023-12-21Complexity Theory Explained Visually | P vs NP
2023-12-19I asked AI to draw itself (DALL·E 2) #aiart
2023-12-19Origin of Batteries
2023-12-17Computers can't roll dice
2023-12-14Why Deep Neural Networks Beat Shallow Ones. #ai #technology #science
2023-12-12How AI Systems Represent Concepts #ai #ailearning
2023-12-11Discovery Of Electric Motors #physics #electricalengineering #science #technology
2023-12-09Is Intelligence related to prediction? #ai #chatgpt #technology #ailearning
2023-12-07The only AI moat is Community #ai #education #chatgpt
2023-12-06Designing Educational Experiences with Pixar and Khan Academy | Brit Cruise Google Talk
2023-12-05Why Bitcoin has Value #bitcoin #bitcoinnews #bitcoinmining


Tags:
big o notiation
complexity theory
p vs np
p = np
exponential growth
non deterministic machine
polynomial growth