P vs. NP: The Biggest Puzzle in Computer Science

Поделиться
HTML-код
  • Опубликовано: 13 май 2024
  • 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/
  • НаукаНаука

Комментарии • 600

  • @QuantaScienceChannel
    @QuantaScienceChannel  5 месяцев назад +60

    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
      @santmat007 4 месяца назад +1

      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
    @iamtheusualguy2611 5 месяцев назад +878

    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
      @0ptimal 5 месяцев назад +32

      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
      @smaquasim1745 5 месяцев назад +11

      In Sha Allah you will solve this

    • @samtonetto3294
      @samtonetto3294 5 месяцев назад +21

      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
      @ArawnOfAnnwn 5 месяцев назад

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

    • @JesterFlemming
      @JesterFlemming 5 месяцев назад +7

      @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
    @brodie3088 5 месяцев назад +348

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

    • @weqe2278
      @weqe2278 Месяц назад +1

      You would fail....

    • @brodie3088
      @brodie3088 Месяц назад +94

      @@weqe2278just like you failed at getting the joke

    • @wadewilson6320
      @wadewilson6320 Месяц назад +24

      Go for it, Will.

    • @CaesarIscariot
      @CaesarIscariot Месяц назад +21

      Good, Will

    • @sh2157
      @sh2157 Месяц назад

      ​@@weqe2278How do you like them apples! 🍎

  • @patrickgambill9326
    @patrickgambill9326 5 месяцев назад +831

    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
      @TheEzypzy 5 месяцев назад +11

      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
      @patrickgambill9326 5 месяцев назад +54

      @@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
      @play005517 5 месяцев назад +7

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

    • @johannes960
      @johannes960 5 месяцев назад +2

      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
      @Shrey237 5 месяцев назад +4

      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.

  • @manolismylonas9886
    @manolismylonas9886 4 месяца назад +53

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

    • @asadsabir7718
      @asadsabir7718 10 дней назад +1

      If I was ever getting a tattoo, it would be the formula for entropy

  • @goGOgetITnow
    @goGOgetITnow 5 месяцев назад +114

    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.

  • @sunkruhmhalaci2592
    @sunkruhmhalaci2592 5 месяцев назад +305

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

    • @farrel_ra
      @farrel_ra 4 месяца назад +9

      I agree with u, The Imitation Game tells it.

    • @reh3884
      @reh3884 4 месяца назад +50

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

    • @antiabrahamicreligion
      @antiabrahamicreligion 4 месяца назад +10

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

    • @BG-kj5wb
      @BG-kj5wb 4 месяца назад +31

      @@bennyklabarpan7002 Genuinely interested in your perspective. Are you saying as a net no lives were saved (ally and axis combined) or no lives even of the allies were saved? My assumption was he did save allies' lives indirectly and did have a hand in winning the war for the allies.

    • @BG-kj5wb
      @BG-kj5wb 4 месяца назад +29

      @@bennyklabarpan7002 what makes you say the conflict was prolonged by Turing though?

  • @petergibson2318
    @petergibson2318 4 месяца назад +31

    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
      @sk-sm9sh Месяц назад +3

      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
      @rongarza9488 Месяц назад +1

      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
      @Am33304 22 дня назад

      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.

    • @vlc-cosplayer
      @vlc-cosplayer 12 дней назад

      It's always about semantics, isn't it? 💀

  • @suzannecarter445
    @suzannecarter445 5 месяцев назад +22

    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.

  • @QuantaScienceChannel
    @QuantaScienceChannel  5 месяцев назад +4

    Quanta is conducting a series of surveys to better serve our audience. Take our video audience survey and you will be entered to win free Quanta merchandise: quantamag.typeform.com/video

  • @Salted_Potato
    @Salted_Potato 5 месяцев назад +87

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

  • @KeemDaDream568
    @KeemDaDream568 5 месяцев назад +15

    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
      @f.mckenzie4212 23 дня назад

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

  • @djdedan
    @djdedan 5 месяцев назад +14

    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.

  • @wunhopkuendo2840
    @wunhopkuendo2840 5 месяцев назад +3

    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
    @prayagbhatt5759 5 месяцев назад +22

    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
    @TomiTapio 2 месяца назад +5

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

  • @Rarests
    @Rarests 6 дней назад +1

    I love how he says 'if humanity survives long enough'. Great reminder, we really need to do better.

    • @billycox475
      @billycox475 5 дней назад

      I'll get right on it 😉

  • @kenkiarie
    @kenkiarie 5 месяцев назад +16

    Phenomenal visuals and amazingly concise definition. Simply beautiful.

  • @oldbrokenhands
    @oldbrokenhands Месяц назад +2

    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.

  • @dekev7503
    @dekev7503 2 месяца назад +1

    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.

  • @schunka1051
    @schunka1051 Месяц назад +1

    the quality of these videos is so incredible

  • @TankorSmash
    @TankorSmash 5 месяцев назад +8

    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!

  • @bayleemeacham6104
    @bayleemeacham6104 18 дней назад

    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
    @dominicbravoclips1264 5 месяцев назад +1

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

  • @keyboard_toucher
    @keyboard_toucher 2 месяца назад +3

    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
      @brianb.6356 Месяц назад +2

      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.

  • @yash1152
    @yash1152 5 месяцев назад +2

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

  • @juancarlospizarromendez3954
    @juancarlospizarromendez3954 5 месяцев назад +5

    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.

  • @goplex1
    @goplex1 Месяц назад

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

  • @sarthakjain1824
    @sarthakjain1824 5 месяцев назад +41

    Absolutely fascinating video, animators deserve a raise

  • @younesmdarhrialaoui643
    @younesmdarhrialaoui643 5 месяцев назад +1

    This was an amazing video. Thank you!

  • @a4ldev933
    @a4ldev933 4 месяца назад +1

    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.

  • @blaxbrian6877
    @blaxbrian6877 5 месяцев назад

    Thank you for imparting this knowledge to me.

  • @jadeyjung
    @jadeyjung 5 месяцев назад

    this
    is
    QUANTA
    truly thanks for this amazing summary!

  • @abraruralam3534
    @abraruralam3534 4 месяца назад +2

    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.

  • @renaldyazhari2709
    @renaldyazhari2709 5 месяцев назад +3

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

  • @cannyp3
    @cannyp3 5 месяцев назад

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

  • @TheBooker66
    @TheBooker66 5 месяцев назад

    Great video (as always)!

  • @PeymanSayyadi
    @PeymanSayyadi 5 месяцев назад

    Beautiful video; thanks for sharing.

  • @GabrielDucharme
    @GabrielDucharme 5 месяцев назад

    Beautifully explained

  • @dickybannister5192
    @dickybannister5192 5 месяцев назад

    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

  • @ckq
    @ckq 5 месяцев назад

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

  • @theekshanabandara9293
    @theekshanabandara9293 5 месяцев назад

    Very informative! ❤

  • @riccardofoschi
    @riccardofoschi 5 месяцев назад +1

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

  • @charlesssgraham
    @charlesssgraham 5 месяцев назад +2

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

  • @andrewdeneve7274
    @andrewdeneve7274 5 месяцев назад +22

    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
      @reh3884 4 месяца назад

      No, it isn't.

  • @halamish1
    @halamish1 3 месяца назад

    Excellent presentation

  • @Honest_Reply900
    @Honest_Reply900 2 месяца назад

    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

  • @Misanthrope84
    @Misanthrope84 5 месяцев назад +2

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

  • @ben_spiller
    @ben_spiller 5 месяцев назад

    They got Scott Aaronson. Nice.

  • @livehappy1415
    @livehappy1415 Месяц назад

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

  • @sohailshaikh786
    @sohailshaikh786 5 месяцев назад +1

    Nice summary

  • @vlc-cosplayer
    @vlc-cosplayer 12 дней назад

    "Wow, imagine how many things we could do if P = NP!"
    *Jevons' paradox's honest reaction:*

  • @mdb1239
    @mdb1239 2 месяца назад

    Excellent & thanks.

  • @h_maina
    @h_maina 5 месяцев назад

    Now this is my type of video

  • @zainabomar1283
    @zainabomar1283 5 месяцев назад

    great explanation

  • @user-zb2st6zi6j
    @user-zb2st6zi6j 5 месяцев назад

    Nice. Well done.

  • @abdelkaioumbouaicha
    @abdelkaioumbouaicha 5 месяцев назад +6

    📝 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)

  • @svevamorini5710
    @svevamorini5710 3 месяца назад

    this video is GOLD

  • @ValidatingUsername
    @ValidatingUsername 5 месяцев назад

    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.

  • @chickenlittle4344
    @chickenlittle4344 5 месяцев назад

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

    • @michaeldebellis4202
      @michaeldebellis4202 5 месяцев назад

      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.

  • @elliotn7578
    @elliotn7578 2 месяца назад +1

    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.

  • @Hippida
    @Hippida 5 месяцев назад

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

  •  5 месяцев назад +3

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

  • @rtsesmelis
    @rtsesmelis Месяц назад

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

  • @forthehomies7043
    @forthehomies7043 5 месяцев назад +1

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

  • @Johnithinuioian
    @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.

  • @laalbujhakkar
    @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!

  • @MyTechieSide
    @MyTechieSide 3 месяца назад +1

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

  • @youssifgamal8545
    @youssifgamal8545 4 месяца назад

    best one I have seen so far regarding P vs NP

  • @user-cg4il5ib8d
    @user-cg4il5ib8d 2 месяца назад

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

  • @alephc
    @alephc 5 месяцев назад +1

    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
      @alephc 5 месяцев назад +1

      P=NP

  • @NikolajKuntner
    @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.

  • @tim40gabby25
    @tim40gabby25 3 месяца назад

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

  • @palancar4262
    @palancar4262 3 месяца назад

    Curious about the MCSP. Seems there are a lot of shortcuts an algorithm could take, ruling out entire branches of possible answers early. I don't doubt that it is NP complete but I'm not seeing why.

  • @naineshrathod2392
    @naineshrathod2392 2 месяца назад

    I would like to read more about theoretical computer science research papers.
    Where can I find information and material or content about theoretical computer science.
    I would also like to know about the current ongoing research
    Please share some resources about this!!

  • @jurycould4275
    @jurycould4275 3 месяца назад +3

    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.

  • @PanduPoluan
    @PanduPoluan 5 месяцев назад +1

    So, the halting problem can be solved?

  • @FD-rt3rv
    @FD-rt3rv 5 месяцев назад

    very nice!!!

  • @Afauci
    @Afauci 3 месяца назад

    Awesome!

  • @burnstick1380
    @burnstick1380 4 месяца назад

    9:20 shortest path on a map? uhhh you heard of the Traveling Salesman problem right? Or is this (theoretical) computable?

    • @opusdei1151
      @opusdei1151 4 месяца назад

      I would say those are two different problems. Salesman problem is in a loop. The other one connects two points and the routs between them.

  • @bvanhise
    @bvanhise 4 месяца назад

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

  • @AlexandreFerreira-jb2jl
    @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.

  • @mamavscience2977
    @mamavscience2977 5 месяцев назад

    So, if the universe is fundamentally quantum, then you could say that classical reality is just a subset of it that is conveniently described by p-type setups. The rest would have to be represented on a quantum computer, in quantum simulations. Or am I missing something?

  • @SolaceEasy
    @SolaceEasy 4 месяца назад

    Wisdom traditions around the world have grappled with the issue.

  • @josephclauson452
    @josephclauson452 4 месяца назад +1

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

  • @Robert_McGarry_Poems
    @Robert_McGarry_Poems 5 месяцев назад

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

  • @beni22sof
    @beni22sof 2 месяца назад +1

    If P=NP that does not mean that the polynomial time solution is within reach. Polynomials of high degree also grow fast...

  • @pgirard1227
    @pgirard1227 5 месяцев назад

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

  • @KillianTwew
    @KillianTwew 5 месяцев назад +2

    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.

  • @joelcoady
    @joelcoady 3 месяца назад

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

  • @OK-ri8eu
    @OK-ri8eu 5 месяцев назад

    Ah I like this, I remember taking my Algorithms course and being introduced to such a problem it's amazing. Thanks for the video!

  • @wzywg
    @wzywg 5 месяцев назад

    Read Turing's Cathedral by George Dyson, great coverage of the history of the modern computer.

  • @shadeblackwolf1508
    @shadeblackwolf1508 4 месяца назад

    There are a good chunk of standard gates, in boolean logic, but foundationally you only need 2. Not, and either and, or or. You can construct the other with these parts. Or for example is not(not A and not B) the and only returns true now if both A and B are false, meaning the whole construct becomes an or. The same trick can create and from or

  • @caspermadlener4191
    @caspermadlener4191 5 месяцев назад +4

    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.

  • @dickybannister5192
    @dickybannister5192 5 месяцев назад

    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.

  • @JustAnotherAlchemist
    @JustAnotherAlchemist 5 месяцев назад +1

    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
      @roberth5435 5 месяцев назад +6

      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.

  • @lasquetygaming9234
    @lasquetygaming9234 5 месяцев назад

    Maybe the two scenarios has an connection to each other? Like if i have an solution or if i solved an complex problem,i would easily and more faster solve the problem.But if you had like no solution at all then it would be hard and it would take time to solve the problem? So maybe P=NP:P≠NP indicating that there's some relationship with the two scenarios?

  • @ADthehawk
    @ADthehawk 5 месяцев назад +2

    Well, proving P=NP alone wouldn't do much of what you were saying. We would still need to figure out the specific algorithms (I don't think the proof, if it exists, will also provide a template to "convert" all NP problems to P problems).

    • @jacobbass8106
      @jacobbass8106 4 месяца назад +1

      I believe the idea is that the algorithm itself is the way to prove P=NP. Another way to say it is, how could you prove P=NP without such algorithm?

  • @roccobierman4985
    @roccobierman4985 4 месяца назад +1

    What about quantum computers and q-bits?

  • @yash1152
    @yash1152 5 месяцев назад

    12:12 will this vid give definitien of NP-hard & NP-complete? lets see.