ImmersiveAmbientModecolor: #aca0b9 (color 1)
Video Format : 22 (720p) openh264 ( https://github.com/cisco/openh264) mp4a.40.2 | 44100Hz
Audio Format: Opus - Normalized audio
PokeTubeEncryptID: 4c9d535c3ece9c0f685010b1901c7c0f145be28cd37ee9d3fa0cb52a72dc78b7b4f4fbad2e8f6da13b420734f8ae1b28
Proxy : eu-proxy.poketube.fun - refresh the page to change the proxy location
Date : 1715635809032 - unknown on Apple WebKit
Mystery text : cFFzZHlnYVljRTQgaSAgbG92ICB1IGV1LXByb3h5LnBva2V0dWJlLmZ1bg==
143 : true
651,106 Views ⢠Dec 1, 2023 ⢠Click to toggle off description
This video covers a wide range of topics including: the history of computer science, how transistor-based electronic computers solve problems using Boolean logical operations and algorithms, what is a Turing Machine, the different classes of problems, circuit complexity, and the emerging field of meta-complexity, where researchers study the self-referential nature of complexity questions.
Featuring computer scientist Scott Aaronson (full disclosure, he is also member of the Quanta Magazine Board). Check out his blog: scottaaronson.blog/
Read the companion article about meta-complexity at Quanta Magazine: www.quantamagazine.org/complexity-theorys-50-year-âŚ
00:00 Introduction to the P vs NP problem
02:16 Intro to Computational Complexity
02:30 How do computers solve problems?
03:02 Alan Turing and Turing Machines
04:05 George Boole and Boolean Algebra
05:21 Claude Shannon and the invention of transistors
06:22 John Von Neumann and the invention of the Universal Electronic Computer
07:05 Algorithms and their limits
08:22 Discovery of different classes of computational problems
08:56 Polynomial P problems explained
09:56 Exponential NP Problems explained
11:36 Implications if P = NP
12:48 Discovery of NP Complete problems
13:45 Knapsack Problem and Traveling Salesman problem
14:24 Boolean Satisfiability Problem (SAT) defined
15:32 Circuit Complexity Theory
16:55 Natural Proofs Barrier
17:36 Meta-complexity
18:12 Minimum Circuit Size Problem (MCSP)
- VISIT our Website: www.quantamagazine.org/
- LIKE us on Facebook: www.facebook.com/QuantaNews
- FOLLOW us Twitter: twitter.com/QuantaMagazine
Quanta Magazine is an editorially independent publication supported by the Simons Foundation: www.simonsfoundation.org/
Views : 651,106
Genre: Science & Technology
Date of upload: Dec 1, 2023 ^^
Rating : 4.929 (378/21,007 LTDR)
RYD date created : 2024-05-13T20:41:52.816746Z
See in json
YouTube Comments - 599 Comments
Top Comments of this video!! :3
As a CS graduate student, the theoretical sections of the field are quite mind-bending and very profound in a way. I thnink often times people underestimate what deep insights questions in computer science can give back to the world. Thank you for showing such a nice summary of one of them!
876 |
I might take a crack at this on a chalkboard while I'm working my janitor job at MIT
344 |
This video is good, but a few small details to add.
1. Solving P vs NP doesn't mean all encryption breaks overnight. RSA encryption could be broken if a polynomial algorithm is found for an np complete problem, but only if the polynomial isn't too big. Even polynomial algorithms can be unusable in practice. This is all assuming an explicit constructive proof P = NP is found. Non constructive proofs will not help solve any of the real world problems, and if it is shown P is not equal to NP, nothing will change. Even if an algorithm to break RSA is found, we can build other encryption methods using NP Hard problems like Travelling Salesman Problem (shortest path version).
2. The Travelling Salesman Problem (TSP) is NP hard in it's usual statement. It is only NP complete if you ask the question "is it possible to find a path that is shorter than a given length". If you ask the problem of finding the shortest path, this is not verifiable in polynomial time.
829 |
So glad to see Shannon mentioned. He is massively underrated, he basically is the father of modern computers (let alone Communication and Information Theory)
53 |
Turing was brilliant and saved untold lives in WWII with his encryption work. How they treated him was horrible.
305 |
Im a teacher and I have to applaud your video style. It's excellent from an educational perspective with very sharp and clear visualisations and superb pace. Bravo.
114 |
I love how he says 'if humanity survives long enough'. Great reminder, we really need to do better.
1 |
This was excellent! Scott Aaronson praised it highly for accuracy but did state that it would have been improved by addressing the difference between Turing machines and circuits (i.e., between uniform and non-uniform computation), and where the rough identities âpolynomial = efficientâ and âexponential = inefficientâ hold or fail to hold.
22 |
Clearest explanation Iâve seen. Maybe it couldâve been paced slightly slower at points but nothing a manual pause and rewind wonât fix.
14 |
His last question "Will we be able to understand the solution?" is the most profound question of all.
It reminds me of the computer "Deep Thought" in "The Hitchiker's Guide to the Galaxy" which spent generations trying to solve the problem of "Life the Universe and Everything".
After many hundreds of years it came up with the answer.....42.
But what does THAT mean ????
31 |
What a well constructed video. I appreciate how it went from basic Computer Science knowledge and gradually introduced higher level Computer Science topics in a simply put way.
15 |
Best video Iâve seen in a long time. Honestly. Great, on the point presentation of distinct very important, fundamental concepts of our time
3 |
One of the best explanations of P, NP. I recalled my Theory of Computation, Information Security lectures and found it really fascinating. The insights are really cool and best explained. Thank you so much !!!
22 |
Its mind boggling how many consistently great videos Quanta Magazine puts out frequently. Thank you for this gift to the world.
87 |
Phenomenal visuals and amazingly concise definition. Simply beautiful.
16 |
Youâre video is great. My professor was talking about this in class, and you went into so much detail. I like the parts you included with the other guy too. The back and forth was cool!
|
Im an electrical engineering graduate besides understanding in electricity what really shakes me is understanding of how computer thinks. I really love it as side hobby. đ
1 |
This video greatly overblows the real-world significance of P vs. NP. The question is a very theoretical one and, although it would be unintuitive to learn that P = NP, it is by no means a given that a proof of P = NP would leap down from the ivory tower and cause any direct or "overnight" effect at all on the internet, AI applications, business, cryptography, etc. For people other than academics to care, we would need to see new algorithms that are actually greatly more efficient on real-world problems than current real-world approaches are, but no such algorithm is necessarily provided by a proof in this area regardless of its conclusion.
3 |
Did NOT expect a Boolean logic primer in a P versus NP video. đ
5 |
@QuantaScienceChannel
5 months ago
Read about about "Complexity Theoryâs 50-Year Journey to the Limits of Knowledge" at Quanta Magazine: www.quantamagazine.org/complexity-theorys-50-year-âŚ
60 |