P vs. NP: The Biggest Puzzle in Computer Science

Are there limits to what computers can do? How complex is too complex for computation? The question of how hard a problem is to solve lies at the heart of an important field of computer science called Computational Complexity. Computational complexity theorists want to know which problems are practically solvable using clever algorithms and which problems are truly difficult, maybe even virtually impossible, for computers to crack. This hardness is central to what’s called the P versus NP problem, one of the most difficult and important questions in all of math and science.
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/comple...
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: / quantanews
- FOLLOW us Twitter: / quantamagazine
Quanta Magazine is an editorially independent publication supported by the Simons Foundation: www.simonsfoundation.org/

[@QuantaScienceChannel]

Read about about "Complexity Theory’s 50-Year Journey to the Limits of Knowledge" at Quanta Magazine: www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/

[@santmat007]

Confused Here... Please Help... ???? First Statement of Logical Facts and Action in the Video... ""A Robot arrives in a foreign land where everyone either always tells the truth or always lies. The robot reaches a fork in the road with two choices. One path leads to safety in the land of truth tellers, while the other leads to doom in the land of liars. A sentry appears. But it is unclear which group they belong too."" What question can the robot ask to determine the safe route." Q1. Which path leads to the land of liars? Q2. Are you a liar or a truth teller? Q3. Which path leads to your home? Number 3 is the videos answer to robot's quandary... But WTF? THE SENTRY COULD BE LYING AND POINTING OUT THE WRONG PATH TO HIS HOME.... SINCE HE COULD BE FROM THE LIARS GROUP. How does the video factually, logically, conclude from the stated logic RULES prior to the tested answer... That it is SAFE to go right. Why is it safe to go right. HELLO ? I don't see the robot being able to correctly draw a conclusion from the facts give up to that point ????????? So how can we move on to multiple sentries if the prior action is based on a logical fallacy ????

[@iamtheusualguy2611]

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!

[@0ptimal]

Yes. People assume human creations are somehow unnatural, but many if not all are an interation of natures patterns. We have an innate desire to express them, or their expression is just inevitable. The further we go the more we realize we are just creating something already created. In a way, unraveling the story the universe is trying to tell us.

[@smaquasim1745]

In Sha Allah you will solve this

[@samtonetto3294]

I think Theoretical Computer Science is as fundamental to the nature of the reality as Physics. These days more and more physicists look at problems through the lens of information theory and computational complexity.

[@ArawnOfAnnwn]

@@test-zg4hv Wait when did we get sex robots? Where can I buy one right now? 😅😁

[@JesterFlemming]

@iamtheusualguy2611 Absolutely. When I started studying CS I had a hard time with mathematics and didn't see much use of all the theoretical parts. But it didn't last long until I've seen the wonders of Logic, Complexity- and Computability-Theory. I consider them the absolute highlights of my time at university, and it often felt like some kind of mathematical philosophie, so deep were the results I learnt there. I wish more people would know about the deep wonders of theoretical computer science.

[@brodie3088]

I might take a crack at this on a chalkboard while I'm working my janitor job at MIT

[@weqe2278]

You would fail....

[@brodie3088]

@@weqe2278just like you failed at getting the joke

[@wadewilson6320]

Go for it, Will.

[@CaesarIscariot]

Good, Will

[@sh2157]

​@@weqe2278How do you like them apples! 🍎

[@patrickgambill9326]

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.

[@TheEzypzy]

If TSP Shortest Path is NP-Hard due to the complexity of verifying a solution, wouldn't that render it unusable for encryption, as quick verification is a requirement?

[@patrickgambill9326]

@@TheEzypzy No. If you actually know the solution, it is easy to verify. If you do not know the actual solution, it is hard to verify if a proposed solution is actually a solution. If I know the actual shortest path, it is easy to see if someone else found the same shortest path. What is hard is if I do not know the shortest path, but I have a pretty short path, how do I ensure it is actually shortest.

[@play005517]

​@@patrickgambill9326how do you verify(for yourself or others) the answer you claim to be correct is actually correct

[@johannes960]

yeah you're right:) Like the proof that LPs can be solved in poly time:) Its nice to know but the algorithm is unusuable compared to the Simplex Alg:)

[@Shrey237]

I think RSA is Co-NP not NP and can be solved by Shor's Algorithm in polynomial time, but more recently there have been proposals for quantum safe cryptography that use random walks in higher dimensions with secret basis vectors, I think.

[@sunkruhmhalaci2592]

Turing was brilliant and saved untold lives in WWII with his encryption work. How they treated him was horrible.

[@farrel_ra]

I agree with u, The Imitation Game tells it.

[@bennyklabarpan7002]

What? He didn't save any lives in WW2

[@reh3884]

@@bennyklabarpan7002 Many, many lives were saved because of Alan Turing and his team in breaking the Enigma code.

[@bennyklabarpan7002]

@@reh3884 Not at all, it just prolonged the war

[@antiabrahamicreligion]

​@@bennyklabarpan7002 still doesn't change how much he contributed to science

[@manolismylonas9886]

So glad to see Shannon mentioned. He is massively underrated, he basically is the father of modern computers (let alone Communication and Information Theory)

[@goGOgetITnow]

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.

[@petergibson2318]

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

[@sk-sm9sh]

42 just means that author of The Hitchiker's Guide to the Galaxy ran out of ideas what to write so he thrown a dice and put down the value he got.

[@rongarza9488]

Exactly! Let's say that matter and energy sprout out of nothing, and both can cancel out. What made them separate to start with, and rejoin later? c? the speed of light? c can survive any black hole, but we can't appreciate the speed of light as a "thing". So 42 could be an answer but we can't understand that as a solution.

[@Am33304]

It means that the person who posed the question and the brainy computer were functional idiots. Garbage in and out. In other words, bad question, bozo.

[@suzannecarter445]

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.

[@Salted_Potato]

Its mind boggling how many consistently great videos Quanta Magazine puts out frequently. Thank you for this gift to the world.

[@codycast]

lol settle down

[@Salted_Potato]

@@codycast no thanks

[@djdedan]

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.

[@kenkiarie]

Phenomenal visuals and amazingly concise definition. Simply beautiful.

[@wunhopkuendo2840]

Best video I’ve seen in a long time. Honestly. Great, on the point presentation of distinct very important, fundamental concepts of our time

[@prayagbhatt5759]

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 !!!

[@TomiTapio]

Did NOT expect a Boolean logic primer in a P versus NP video. 🎉

[@KeemDaDream568]

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.

[@f.mckenzie4212]

Watching a video on advanced computer science topics and not knowing how to adjust the playback speed on youtube is making me laugh

[@schunka1051]

the quality of these videos is so incredible

[@TankorSmash]

This is an amazing video, I'm really impressed by the quality of the animations and explanations. Thank you for putting the time in to make this!

[@oldbrokenhands]

Thanks for this, when I took computer science classes at UTD, this was glossed over in a slide, and given maybe two sentences in the textbook.

[@keyboard_toucher]

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.

[@brianb.6356]

A proof doesn't even prove that such algorithms exist. P == NP is not the same thing as P-with-very-small-exponents == NP. It could be that the knapsack problem is in P because someone finds an O(n^10,000,000) algorithm. This would be a constructive proof that P == NP but also have essentially no practical implications.

[@bayleemeacham6104]

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!

[@dominicbravoclips1264]

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. 😊

[@dekev7503]

I briefly dabbled into this topic in a Computer arithmetic hardware implementation course that I took in grad school ( MS Microelectronics Engineering) . Mainly the part on circuit complexity ( as that was the applicable concept to the course). It’s was a really interesting topic/course, especially the part of the course where I got to optimise a hardware implementation of an FFT algorithm on an FPGA by applying the techniques in the course.

[@abraruralam3534]

it's fun looking into the CSAT problem and trying to figure out exactly why you can't just assume the output to be 1 and trace it back to a random possible input combination. It eventually comes down to these two facts: ----------------------------------------------------------------------- 1. logic gate outputs can get shared between logic gate inputs. E.g: say, the output of an OR gate is connected to 2 (or more) AND gate inputs. 2. Logic gates AND and OR have multiple inputs mapped to their outputs. This means, they are many-to-one functions and do not have inverse functions. As a result, when you try to trace back from a given output, you have to randomly guess an input every time. This wouldn't be a problem on its own but due to our first point (logic gate outputs can get shared between logic gate inputs), when two guessed inputs end up meeting at a common output, they won't necessarily match so you end up with 1 and 0 being output value simultaneously. And that's where the computational complexity increases drastically, because now you have to keep an account of all those common outputs branching into multiple inputs, so that your guessed inputs align when they meet there.

[@yash1152]

2:17 study of inherent resources, such as T & S needed to solve a computational problem woah woah, so precisely put definition. awesome.

[@goplex1]

Thank you for a great explanation of p vs np! Never got it during my computer science studies

[@sarthakjain1824]

Absolutely fascinating video, animators deserve a raise

[@destructionman1]

On it ..

[@juancarlospizarromendez3954]

I have discovered that some programs have parts of code of P class and parts of code of NP class. There are classes of relaxations that use heuristics that can solve some problems but with no warranty about its success or about its optimality.

[@jadeyjung]

this is QUANTA truly thanks for this amazing summary!

[@blaxbrian6877]

Thank you for imparting this knowledge to me.

[@abdelkaioumbouaicha]

📝 Summary of Key Points: 📌 The P versus NP problem is a conundrum in math and computer science that asks whether it is possible to invent a computer that can solve any problem quickly or if there are problems that are too complex for computation. 🧐 Computers solve problems by following algorithms, which are step-by-step procedures, and their core function is to compute. The theoretical framework for all digital computers is based on the concept of a Turing machine. 🚀 Computational complexity is the study of the resources needed to solve computational problems. P problems are relatively easy for computers to solve in polynomial time, while NP problems can be quickly verified if given the solution but are difficult to solve. 🌐 The P versus NP problem asks whether all NP problems are actually P problems. If P equals NP, it would have far-reaching consequences, including advancements in AI and optimization, but it would also render current encryption and security measures obsolete. 💬 Circuit complexity studies the complexity of Boolean functions when represented as circuits, and researchers study it to understand the limits of computation and optimize algorithm and hardware design. 📊 The natural proofs barrier is a mathematical roadblock that has hindered progress in proving P doesn't equal NP using circuit complexity techniques. 🧐 Meta-complexity is a field of computer science that explores the difficulty of determining the hardness of computational problems. Researchers in meta-complexity are searching for new approaches to solve important unanswered questions in computer science. 📊 The minimum circuit size problem is interested in determining the smallest possible circuit that can accurately compute a given Boolean function. 📣 The pursuit of meta-complexity may lead to an answer to the P versus NP problem, raising the question of whether humans or AI will solve these problems and if we will be able to understand the solution. 💡 Additional Insights and Observations: 💬 "The solution to the P versus NP problem could lead to breakthroughs in various fields, including medicine, artificial intelligence, and gaming." 🌐 The video mentions the concept of computational complexity theorists wanting to know which problems are solvable using clever algorithms and which problems are difficult or even impossible for computers to solve. 🌐 The video highlights the potential negative consequences of finding a solution to the P versus NP problem, such as breaking encryption and security measures. 📣 Concluding Remarks: The P versus NP problem is a significant conundrum in math and computer science that explores the possibility of inventing a computer that can solve any problem quickly. While finding a solution could lead to breakthroughs in various fields, it could also have negative consequences. The video discusses computational complexity, circuit complexity, and meta-complexity as areas of study that may contribute to solving this problem. The pursuit of meta-complexity raises questions about whether humans or AI will solve these problems and if we will be able to understand the solution. Generated using Talkbud (Browser Extension)

[@younesmdarhrialaoui643]

This was an amazing video. Thank you!

[@andrewdeneve7274]

I think an important point to be made in the field of algorithms is that a lot of the efficiency of certain algorithms depends on input size. Theoretically, if you have a P problem and an NP problem that solve the same problem, the P problem runs in n^200 time whereas the NP problem runs in 2^n time, if your input size is always small, say 2 or 3, then actually the NP problem is more efficient. You can also apply this idea to just the area of P problems - for example with sorting algorithms, if we know the input size will always be very small, sometimes it is more efficient to use what is learned as the “slow” algorithms (like selection sort/ bubble sort) vs the “fast” algorithms like merge sort or quicksort. Some may argue this can’t be since bubble sort runs in n^2 vs merge sort running in nlogn , so merge sort is always at least as good, however there are also hidden constants in these runtimes that get overlooked easily. You should really see the runtimes as (n^2 + c) and (nlogn + d) respectively, where c and d are constants and c < d. You can see the constants as additional overhead needed to set up the algorithm. in academia we usually ignore the constants as n grows large, but in practice, there may be cases where n is guaranteed to be small to the point where it is actually more efficient to use the simpler “slower” algorithm. A good analogy that my professor made is why use a sledgehammer to pound in a nail when a regular hammer will do. ( this also applies to deciding which kinds of data structures to use) Anyways nicely made video! 👍

[@reh3884]

No, it isn't.

[@cannyp3]

Great quick explanation of SAT! Not as easy at it looks.

[@a4ldev933]

There are some contradictory statements in your video, but it is a great presentation of N and NP problems. Thank you for creating such a wonderful explanation in layman's terms.

[@PeymanSayyadi]

Beautiful video; thanks for sharing.

[@riccardofoschi]

who made the animation in this video is a genius. As well as the people behind the script!! Great job!

[@ben_spiller]

They got Scott Aaronson. Nice.

[@TheBooker66]

Great video (as always)!

[@ckq]

I just saw Scott Aaronson 5 days ago (when this was released) at UT and studied P vs NP. nice timing

[@GabrielDucharme]

Beautifully explained

[@Misanthrope84]

Beautiful work, managed to explain a very complex idea in simple terms and animation. Bravo 👏

[@charlesssgraham]

Okay, can we talk about how cool this animation is though??

[@dickybannister5192]

Talking about this stuff reminds me. I think the SAT Solver progress is heavily undersold. both as a technical progression, but it is really, really useful. would love a crash course. thx

[@elliotn7578]

Plain Boolean formulas cannot operate like a Turing machine because they have a fixed bound on computation (once you assign values to the variables you can simplify the expression in a fixed amount of time). For a paradigm to be Turing complete it must be possible for it to run forever, which requires conditional loops. Boolean circuits can be made Turing complete by introducing registers (for memory) and a clock to synchronize computational steps, but they can no longer be represented as pure Boolean formulas.

[@renaldyazhari2709]

Best video ever on the topics of explaining P vs NP problem

[@svevamorini5710]

this video is GOLD

[@livehappy1415]

Such a great video, learned a lot. Can I ask what tools did you use to create such graphics and videos?

[@h_maina]

Now this is my type of video

[@theekshanabandara9293]

Very informative! ❤

[@sohailshaikh786]

Nice summary

[@laalbujhakkar]

A 20 minute video on P vs NP problems that FAILS to first define what P and NP actually stand for. Good job Quanta!

[@halamish1]

Excellent presentation

[@Honest_Reply900]

An awesome video gave a lot of insights on the the kind of problems and it would be nice if the solutions are always used for the benefit of the society

Simple things interacting can lead to complexity and emergence, this applies to algorithms...

[@user-cg4il5ib8d]

For as long as I've known about it the "Is P - NP?" problem has intrigued me.

[@jurycould4275]

It’s not a profound problem. It’s THE most profound problem. If p =/= np, then we are essentially close to the limit and stuck until we disappear.

[@Johnithinuioian]

I think there's a way. Consider that there could be hidden, exploitable structures or patterns in a NP-hard problem (example) that might have less time/space complexity and depends on the input size, algorithm, the exact values/order of the input, and/or more.

[@MyTechieSide]

just one word......."AWESOME"

[@mdb1239]

Excellent & thanks.

[@KillianTwew]

Doing one hard puzzle might take an infinite amount of time, but running an infinite amount of hard puzzles once would give you atleast ONE solution that you can verify.

[@NikolajKuntner]

5:13 You'll have to amend the comment on how "Boolean boolean formulas can operate like a Turing machine." There is something to be said about representation of decision problems (computably enumerable sets being Diophantine), but a fixed circuit has a maximal number of binary inputs, while an abstract Turing machine can be initialized with arbitrary size inputs.

[@user-zb2st6zi6j]

Nice. Well done.

[@bvanhise]

A beautiful Japanese whodunit novel called "The Devotion of Suspect X" highlights this P vs. NP problem wonderfully.

[@zainabomar1283]

great explanation

[@AlexandreFerreira-jb2jl]

Intuitively i would say, there always be problems that are two much dificult to computers to solve. There always will exist NP problems. Even with quantum computers, as computers arquitecture helps finding more complex solutions in polynomial time, it will always raise NP questions. Therefore its like solving all mysteries of life in computational time.

[@Hippida]

Problems such as these are a wonderful conundrum for my little brain to twist and turn and loop around . . . . .

[@caspermadlener4191]

An algorithm having polynomial time is equivalent to the following fact: Doubling you input will multiply the processing time by a bounded amount. Btw, great that the video only focussed on the problem itself, not the prize money.

[@mychannel-te5ke]

I do theoretical computer science research, and I found some of the explanations by the narrator in this video kinda confusing and misleading. Some things are just false. I love your videos, and before I've seen some great explanations about my area of expertise, and I was amazed by how good you manage to collect your sources to make things correct. But this one is sad :(

[@Gin-toki]

Could you elaborate on which parts are wrong/false?

[@Ozay1998]

it boggles me how many people in the comments that call themselves computer scientists call this video „the best explanation there is“ with these heavy mistakes or straight up wrong statements

[@Ozay1998]

@@Gin-tokiproving that proving p=np would just prove that p=np and that’s it. nothing would change overnight. it’s like saying that proving that there exists a solution for a given equation is the same as knowing the solution which is not really true. those polynomial algorithms would still have to be found and also they could be still giga slow in practice. n^10000 is still polynomial but unusable. it would be just be a theoretical result. Actually the methods to prove it would probably be even more interesting

[@theultimatereductionist7592]

As a mathematician and former chemical engineer, I absolutely want P=NP and practical useful algorithms to be found. Billions of important practical engineering and science problems and logistics problems need solving. I couldn't give a shit about encryption. But it is sadly almost certain that P is not equal to NP.

[@forthehomies7043]

You packed so much info in and explained everything so well in under 20 minutes. Nicely done.

[@youssifgamal8545]

best one I have seen so far regarding P vs NP

[@rtsesmelis]

Brilliant video. Think I understood nearly everything. Which says probably more about me than about your video, but still..... Thanks!😂

[@ValidatingUsername]

5:25 "truth circuits" are essentially analogue neural nets that cant take into account partial voltages like digital or biological nodes can to process the input layer and calculate and output.

[@SolaceEasy]

Wisdom traditions around the world have grappled with the issue.

[@JustAnotherAlchemist]

Depending on whether or not the sentry ALWAYS tells lies, or just CAN tell lies, and whether or not you can ask multiple questions, then there can be an optimal guaranteed solution to the problem. All you have to do is ask a question with a known answer. "What is 2+2?" If they give you a false answer, then they lie, and the remaining answers just need to be inverted.

[@roberth5435]

If you are limited to one question, it could be this: "If I asked the other guard which way is the safe path, what would he tell me?" Both guards would point to the unsafe route. Take the other route to safety. I'm not sure the answer in the video is correct.

[@josephclauson452]

Jigsaw puzzles are in P btw, specifically O(n^2).

[@tim_allen_jr]

A problem so great even the universe couldn't figure it out.

[@StarNumbers]

Ok, encryption is important to everybody but the best example is the 3-body problem aka 3-body instability. When you compute the future position of three bodies subject to gravitation you'll get an answer that will always have an error. So now you are searching for an algorithm that will give you zero error. This is easy for two bodies but with three (or more) bodies one must take a time increment and compute the next position at the next time increment that is also the source of the error. Further, the 3-body systems are unstable and chaotic (have no repeating period). Nevertheless you shorten the time increment and lower the error but this will take more time to perform the computation with the result that the error reaches zero when the computing time reaches infinity. Here is a good spot to see that Turing's assertion of giving the computing machine unlimited time in his definition of the universal machine --- *it does not make it universal.* So, ending my comment right here right now is ok and we can "seriously muse" about all this. Unfortunately the cat is out of the bag and implications are fundamental (if not existential). The thing is that our solar system is said to consist of more than two bodies. Ignoring creation/evolution the solar system will break up sooner or later and even theoretically it is now teetering on the edge and can fly apart any minute. Or you can take the 3-body instability as prime reality, chuck the solar system and figure out that the Moon is not a mass rock (hologram image?). Oh, before you call me out as a flat earther, consider that the Earth, Sun, and Moon are three bodies that are working nicely together thank you.

[@Afauci]

Awesome!

[@alephc]

to add consistency: iff constructively solved with small constant/polynom to yield presented disruptions, PKI failure would be no factor anyway because zero-marginal cost economy/society equals non-monetary economy provided the materialized P=NP (non-deterministic processor (NDP)) is public domain, e.g., via IPFS

[@alephc]

P=NP

[@yigithakverdi4154]

Animations so good that I cannot focus on the subject

[@hamedzahmati4530]

Even if P vs NP has positive solution it has just an existential nature. It does not give us a way to contract polynomial-time algorithm for any NP hard ones. There are many problems for which we have the guarantee of solution's existence but yet no one could find it. So even if P VS NP solved there is no immediate danger of losing internet or bank cash.

[@saicharanmarrivada5077]

As Knuth says, existence doesn't necessarily mean embodiment.

[@FD-rt3rv]

very nice!!!

[@JohnSmith-ut5th]

I solved this problem earlier this week. I published my first rough draft earlier this week. It turns out P is not equal to NP. I have rigorously proven it using very advanced mathematics that was thought impossible to do. Amazingly, the proof shows us two amazing facts: all polynomial time problems have optimal substructure and there is an intricate relationship between mathematics we grew up learning: commutativity, associativity, and one more property: logical universality. It turns out, they don't play nice together and therefore P is not equal to NP. You can't have all three properties.

[@Schnorzel1337]

Sure you did.

[@JohnSmith-ut5th]

@@Schnorzel1337 I found a gap in my proof, but it is not a large gap. Basically, I use two way containment to show that P is equivalent to polynomial time dynamic programming. However, one of the directions has a slight mistake in the proof. If I fix that, then yes, I will have proven it. I have spent years and years (decades now) trying to solve this problem chasing it through an amazing journey that I could write a book on. I went through group theory, ring theory, semigroups, magmas, etc.... Honestly, I thought I had proven the opposite, but I realized my attempt to prove P=NP led me to a proof of P!=NP.

[@fragileomniscience7647]

"All polynomial time problems..." By Rices theorem there is no one way to decide whether a problem is in P. On the other hand, that's what natural proofs assume, yet natural proofs have been proven independent of P-NP. Sorry.

[@dariokartal9453]

16:23 What you actually said: "Functions with a number of necessary logic gates grows exponentially with increase in input variables are said to have High Circuit Complexity." Should've said, 'Functions with a number of necessary logic gates that grows exponentially with an increase in the number of input variables are said to have High Circuit Complexity.'

[@chickenlittle4344]

Does this connect with Big O Notation and largely explain the space complexity functions deal with or are these concepts just similar?

[@michaeldebellis4202]

My understanding of Big O notation is you use it to analyze algorithms by stripping away the unnecessary details and keeping the details that matter. The details that matter are what you show with Big O notation. So if you say the performance of some algorithm f with input n = n**2 + 275, the “+ 275” is really irrelevant as n gets large (the difference between 1,000 squared and 1,000 squared + 275 is trivial). So O(f) = n**2 So it is relevant because both are about the computability of an algorithm but P vs. NP describes two sets of problems with radically different performance where as big O notation is a convention for describing performance. But that’s just based on memory so I could be wrong.

[@joelcoady]

Having studied this before I love how well explained this is for people who have no understanding of the field.

[@Robert_McGarry_Poems]

On circuit complexity. Take Boolean algebra and translate it into tri part logic with logarithms. Then quad, and so on...

[@tim40gabby25]

Nice introduction, easy to follow. Like the jigsaw and Sudoku analogies. Just saying.

[@snk-js]

oohh how pleasurable are math videos coming from Quanta Magazine, its like kurzgesagt of numbers

[@andyd3852]

This video brained my damage. In the best of ways.

[@smitpatel1436]

Give raise to the video editor and graphics designer

[@EnricoRodolico]

Fun little fact for the boolean algebra fans out there, AND, OR, and NOT gates form what is called a functionally complete set. There are other functionally complete sets, including entire sets which contain only one gate. NAND and XNOR are two such gates which are able to replace all three of the normal boolean operators through complicated replacement proofs. That is to say, you can construct an AND gate with only NAND gates, along with OR and NOT gates. It's kinda wild really...

[@nasunorahl]

THIS IS WHY every time 'quantum computers' make an advancement in speed on a given type of algorithm traditional programmers quickly improve on the previous system and outperform the quantum advancement. such is life.

[@XOPOIIIO]

Promising a million dollars for the solution is like promising a million dollars for finding infinity stones.

[@dickybannister5192]

nice video, but a brief explanation of what a DTM as opposed to an NTM would have been good. the "mathy" bit of TCS and the "logic" bit don't really bring the subject to life I find. the weird part is that language is both easy to explain and what is actually core, since we both understand language and what it does and that is, basically, what Information Theory is all about. most people would assume Chess or Sudoku or Go or something being the "game" which would best help understand this stuff, or what these guys really want to talk about (even though numbers dont have a mathematical role in Sudoku, they are just "symbols"). Try picking up a "puzzle" magazine and look for Word Ladder. that would be better. there are some great MIT Opencourse lectures on here. you dont need a lot of pre-existing knowledge. also guys like Easy Theory who has some great DFA stuff.

[@user-qv8qc9hv2d]

thank you youtube algorithme for showing me this problem. I didn't even know that this kind of problem existed

[@user-qv8qc9hv2d]

and thank you quantaScience for making this video

[@pgirard1227]

good demo of the bolean cul de sac... We now need a tetravalent logic, independent of its language

[@idegteke]

If you’ve heard about Asimov’s “I, Robot”, the answer is always “My responses are limited, you must ask the right questions” until you finally hear “That, detective, is the right question”. If you are unable find an answer to a question, you should at least consider that you might not be asking the right question to begin with.