P vs. NP and the Computational Complexity Zoo

24 455 Áhorf 2,5 m.

Hackerdashery #2
Inspired by the Complexity Zoo wiki: complexityzoo.uwaterloo.ca/Complexity_Zoo
For more advanced reading, I highly recommend Scott Aaronson's blog, Shtetl-Optimized: www.scottaaronson.com/blog/
Retro-fabulous, cabinet-sized computers:
System/360: en.wikipedia.org/wiki/IBM_System/360
photo: "360-91-panel". Licensed under Public domain via Wikimedia Commons - commons.wikimedia.org/wiki/File:360-91-panel.jpg#mediaviewer/File:360-91-panel.jpg
PDP-8: en.wikipedia.org/wiki/PDP-8
photo: "PDP-8". Licensed under Public domain via Wikimedia Commons - commons.wikimedia.org/wiki/File:PDP-8.jpg#mediaviewer/File:PDP-8.jpg

Protein folding illustration: "Protein folding schematic" by Tomixdf (talk) - Own work (Original text: “self-made”). Licensed under Public domain via Wikimedia Commons - commons.wikimedia.org/wiki/File:Protein_folding_schematic.png#mediaviewer/File:Protein_folding_schematic.png
P vs. NP opinion poll: www.cs.umd.edu/~gasarch/papers/poll2012.pdf


  1. Brandon
    Degi Síðan síðan

    <a href="#" class="seekto" data-time="428">7:08</a> Meanwhile the girls...

  2. Filipe Freitas
    Filipe Freitas
    2 dögum síðan

    Since college Pythagoras theorem was attributed to solve all questions, but my guess is about Bhaskara and 2nd degree equations at first. In the salesman case, from the mattrix generated by the distances between the cities is given the equation, which by classic math have two possible real roots. In a trial with the form ax^2+by+c=0 setting the number of cities, number of distances amongst each other and the number of routes (for 5 cities, 20 distances, and 120 routes), I create a table (mattrix) to the correct manner to index the distances with cities distances by a log in alphabetical order (ab ac ad ae e so on) at the same time obbeying to the crescent order of the values of distances in the form (key_value). In the cartesian plane or by the geographic coordinate system the pythagorean theorem is taken to determine the distances between the points. Then, the low and higher values of the routes through all cities are given by the both roots of the equation. I had try to solve another problems like statistical data (coronavirus pandemic) and the output is equal to official data published and real data observed, as example. For the salesman problem perhaps we get a light for the mathematical logic to find the correct answer or by the way, the true root of the equation.

  3. Krystian Jan
    Krystian Jan
    2 dögum síðan

    Next video related to these problems should be about relation between these P and NP problem and nonlinear quantum computing. Because its not necessarly about time, maybe its ore about let name this 'strongly parallel computing' - nature of time as a quantum parallelism.;)

  4. Raseruuu
    4 dögum síðan

    what if... in Heaven. P= NP

  5. Thiago Amorim
    Thiago Amorim
    5 dögum síðan

    This video is absolutely amazing. Can't believe you stopped making videos.

  6. Sourav Ganguly
    Sourav Ganguly
    6 dögum síðan

    Then we came up with ... Quantum Computing !!!

    1. james yeung
      james yeung
      3 dögum síðan

      still somethings are still unsolvable

  7. River Lance
    River Lance
    6 dögum síðan

    i want to join a coding group , it may be in whatsapp group or else , ; but i dont want to join those group which is by companies or organisation for learning , because mostly people in that group start with "how do i learn to code", but i know coding , just want guys to discuss with ,or maybe share and compete with if anyone has any such groups please i want you to get me a invite i know C,CPP,java , python , a bit about linux and a gamer , i got my data structures down good

  8. abcd xx
    abcd xx
    7 dögum síðan

    I solved NP i will give it to you for a few million dollars contact me on my email def_not_a_scam@gmail.com

  9. Cebo Khumalo
    Cebo Khumalo
    8 dögum síðan

    <a href="#" class="seekto" data-time="505">8:25</a>. i legit went from "P vs NP must be the hardest thing out there". to "What the actual fuck"

  10. SkyLuke
    8 dögum síðan

    How did I not know this channel? Thank you, ISpulse algorithim.

  11. saravan prathi
    saravan prathi
    8 dögum síðan

    The best explanation I could find on this topic on internet!! Thank you! Subscribed..

    9 dögum síðan

    Nice..if it is slow..it would be great

  13. Stephan Kuerner
    Stephan Kuerner
    11 dögum síðan

    Ha Ha Ha - You only have to use 4d algebra and everything is easy to solve. www.ebay.de/itm/192364509549

  14. Hrushikesh Gouda
    Hrushikesh Gouda
    11 dögum síðan

    This is my most favourite ISpulse video. I watch this at least once every month.

  15. Ardor de Leon
    Ardor de Leon
    12 dögum síðan

    <a href="#" class="seekto" data-time="500">8:20</a> you know shirt's getting real when you start drawing dicks and balls

  16. Mohamad Hussein Naim
    Mohamad Hussein Naim
    12 dögum síðan

    What a phenomenal video! It is creators like you that make the internet an awesome place.

  17. Marcus Mitchell
    Marcus Mitchell
    12 dögum síðan

    Really makes you appreciate chess titians on windows vista and seven.

  18. Kenichi Mori
    Kenichi Mori
    13 dögum síðan

    Number zoo is closed number open point.

  19. Sebastian Fernandez Del Castillo
    Sebastian Fernandez Del Castillo
    13 dögum síðan

    WTH is this video about? I'm confused. I just clicked on it.

  20. Francis Paesano
    Francis Paesano
    18 dögum síðan

    This guy is the goat. My punk ass teacher Clyde Kruskal (Department of Computer Science at The University of Maryland) didn't explain shit. He sucks. This video was a life saver.

  21. Moda Foqa
    Moda Foqa
    21 degi síðan síðan

    Solving P vs NP problem actually gonna give you 6 million dollars cuz with solving it will fins solutions to the other 6 problems 😉

    1. james yeung
      james yeung
      19 dögum síðan

      It probably makes you a billionaire since every question ever would be solved

  22. Gelo Domingo
    Gelo Domingo
    22 dögum síðan

    This proved how amazing human brain is, computers cannot replace how human develop bias and it's adaptability

  23. cony.!! pls animes
    cony.!! pls animes
    23 dögum síðan

    to solve p = np is proof if there is a true absolute in the whole all existences. that anything depends on, its kind like the center or the existences and the essence of all essences. Albert Einstein may believe in this kind of god or similar? yeah, why not many things seem that anything is connected in many essence stuff. there is no proof that in some moments that the number pi will have a part that is writing the compilation code 010101 programs of anything a make to become even including matrix human world included or a pokemon fucking Digimon porn.

  24. Bicycle Ninja
    Bicycle Ninja
    23 dögum síðan

    It's kinda like if we could go faster than the speed of light. It would be cool if YOU could do it in your own spaceship, but if everyone and everything did it, the universe would not be as we know it. There would be no organization, no change, no processes, no individuality: all would be everywhere at the same time.

  25. Bicycle Ninja
    Bicycle Ninja
    23 dögum síðan

    Why do I smell chalk?

  26. Souvik Ghosh
    Souvik Ghosh
    23 dögum síðan

    thought the playback speed was high but no that was normal you talk fast 🙃

  27. Omega Fallon
    Omega Fallon
    24 dögum síðan


  28. Max Headrom
    Max Headrom
    24 dögum síðan

    An explanation of algorithm complexity would be great! I know a little about it, but I'm not sure everybody knows.

  29. Max Headrom
    Max Headrom
    24 dögum síðan

    My phone, Samsung S7, is faster than a Cray 3.

  30. Max Headrom
    Max Headrom
    24 dögum síðan

    I'd like to see a video on how FFT killed music! hehehe.

  31. Christopher W
    Christopher W
    24 dögum síðan

    P = NP We're just too stupid right now.

  32. outercloudstudioYT
    24 dögum síðan

    I know the answer! Artificial Neural Networks.

  33. Sujay
    25 dögum síðan

    The creator of this channel is Steven Hazel of Sauce Labs. Happy to see he's doing well for himself

  34. YellowSubmarine
    25 dögum síðan

    Rubiks cubes are np hard <a href="#" class="seekto" data-time="300">5:00</a>...

  35. Problem Shooter
    Problem Shooter
    26 dögum síðan


  36. flying horse
    flying horse
    26 dögum síðan

    OK here is the opinion of someone who doesn't actually have a lot to say A. There is a profound difference between being able to see a solution, even if only in your mind's eye, and just saying there must be an answer. Without a probable answer you can't define the problem. "what's the best move in chess" is a very ill defined question B. Don't use chess as a counter argument to sudocu. One is a static game, the other constantly changing. You refer to pathfinding as a problem solvable by computers. Yes it's possible to define a route in a static environment. Not in an environment where the roots change and the destination keeps relocating and actively trying to get away from you

  37. Corona Virus Respecter
    Corona Virus Respecter
    26 dögum síðan

    My senior physics seminar was on Aaronson’s book QC since Democritus. It’s the only class that ever made me feel like I was having a stroke discussing the book.

  38. cchanc3
    26 dögum síðan

    "if P=NP, then......." I think gets it wrong. It seems intuitive to me that P=NP given enough insight to the algorithm. how hard it is for now I say is irrelevant. I say that chess and sudoku are ultimately P problems that we just haven't solved yet because they're at their core simple arithmetic in closed systems.

  39. No Time
    No Time
    26 dögum síðan

    does NP == Q ?

  40. Bhaskar Tripathi
    Bhaskar Tripathi
    26 dögum síðan

    It is an eye opening video for me. Will watch it multiple times with full concentration to absorb all the stuff again. Adding it to my favorites. Thanks for creating such stuff and making it accessible to all of us for free. It is inspiring stuff !

  41. Rutuparn Pawar
    Rutuparn Pawar
    26 dögum síðan

    Mind = Blown 🤯

  42. aasy jepale
    aasy jepale
    26 dögum síðan

    P =/= NP because girls are basically an infinitely complex puzzle.

    1. james yeung
      james yeung
      19 dögum síðan

      this comment is from 2006

  43. Jason S
    Jason S
    27 dögum síðan

    The best ISpulse video I ever seen.

  44. malek smida
    malek smida
    27 dögum síðan

    this is an amazing video and explanation, thank you so much!

  45. bbruce995
    29 dögum síðan


  46. Ayushman Dash
    Ayushman Dash
    29 dögum síðan

    I think p vs np is a kind of paradox

  47. Paula Rae
    Paula Rae
    Mánuði síðan

    Huh. Go figure. So you are saying that some problems that have human or event input within the problem cannot be solved because their input changes as the problem develops (or is worked out)? As in problem/puzzle-solving because, as, say, the chess or scrabble game progresses, the input into the problem CHANGES the problem from within so that the original problem becomes a different problem than at the initial recognition of the problem?

  48. Parteupites
    Mánuði síðan

    I never learned the division resolving system, i arrived to the university resolving all divisions by a system developed in my mind, still doing it this way and reached second grade equations this way, teachers don´t understand how i can reach the correct results, never learned maths languange and hate it with all my heart, the only way to resolve some problems is to forget all you know about it and try to find another perspective

  49. Garga
    Mánuði síðan

    After this AMAZING video, what I understand about P vs NP in simple terms and examples is: P is like multiplication. You know the rules and they consist of straightforward steps. Follow them and you get the answer. That's how you check it, too. NP is like sudoku. You know the rules, but finding the solution is a process of elimination. You have to find the wrong answers until you're left with only the right ones (for given cells at first, and then the puzzle entirely). And the question is whether you can find a way to skip this process of elimination for NP?

    1. Moses Onche
      Moses Onche
      22 dögum síðan

      Skipping the elimination process would require knowing the limits of the problem. But when limit tends to infinity, there's no other way

    2. compuholic82
      29 dögum síðan

      Yes, it seems like you got it. It would be incredible if it was possible to always skip the elimination process. But it seems unlikely.

  50. Laavanay Aggarwal
    Laavanay Aggarwal
    Mánuði síðan

    I’m a simple man. I see something I don’t understand, I click

  51. debraj011
    Mánuði síðan

    I think im gonna solve this problem someday, I watched ths vid at *2 speed

  52. Piyush Majgawali
    Piyush Majgawali
    Mánuði síðan

    I want the Sudoku book

  53. Kenichi Mori
    Kenichi Mori
    Mánuði síðan

    np = number process. zeroing.

  54. Kenichi Mori
    Kenichi Mori
    Mánuði síðan

    Point process is simplex = np = pp

  55. Claude Müller
    Claude Müller
    Mánuði síðan

    You've piqued my interest.. Please make more videos?

  56. Bill Xu
    Bill Xu
    Mánuði síðan

    <a href="#" class="seekto" data-time="506">8:26</a> is weird

    Mánuði síðan

    Is it just me or is it was hysterical when you said "To me, that's not a very good puzzle" and removed the pieces of the chess board at <a href="#" class="seekto" data-time="200">3:20</a> Also when you use the slate for exponential time at <a href="#" class="seekto" data-time="348">5:48</a>

  58. Lapeez 22
    Lapeez 22
    Mánuði síðan

    The answer is yes. Thank me later

  59. William Gabriel
    William Gabriel
    Mánuði síðan

    Basically giving up on maths and becoming a poet is part of an NP problem

  60. Clorox Bleach
    Clorox Bleach
    Mánuði síðan

    Let P and N = 1 Therefore, P = NP. I'll be expecting my money by tomorrow.

  61. No One
    No One
    Mánuði síðan

    I know you explain everything very clear, but I still can't understand lolll

  62. Allan Brotchie
    Allan Brotchie
    Mánuði síðan

    Might be stupid to comment but my method is simple deduction by adding a dot to represent a number in one of the 9 points in the square like dice to represent the most likely one and every square can have two possible correct numbers that are proven as the puzzle is being completed. I think most people would realise this, or maybe not? In sudoku.

  63. Canorous
    Mánuði síðan

    Maybe you're looking at the picture

  64. Raghavendran T B
    Raghavendran T B
    Mánuði síðan

    Studying complexity is like understanding the mind of God.

  65. Reid Pattis
    Reid Pattis
    Mánuði síðan

    Gosh. I hope the uploader would continue with these amazing, beautiful, masterpiece of videos. All the best to you, sir.

  66. Nicholas Kinney
    Nicholas Kinney
    Mánuði síðan

    recognizing incorrect answers is easier than understanding correct answers. n!=n^2; n==n; which one is easier to solve? now try n!=n-1(n2+2); n==m;

  67. ParkerMagee
    Mánuði síðan

    Can someone please make sure this video is backed up in the library of congress?

  68. AnimeBoi Addict
    AnimeBoi Addict
    Mánuði síðan

    Simple P can be (0 sort of) Then divide by NP N is 1 and P is variable Then answer is simple (0 sort of)p Not all equations has an single answer Now give me my million dollars

  69. sumsam ullah
    sumsam ullah
    Mánuði síðan

    This video is so good that I come back and watch it every now and then. Please make more videos!

  70. Paul Trimble
    Paul Trimble
    Mánuði síðan

    A fantastic explanation! I learned a lot from watching this. Thanks!

  71. Quoss Wimblik
    Quoss Wimblik
    Mánuði síðan

    Cross referencing possibilities from 2 cells in sudoku is more efficient than with one or three cells like crab claws and pincers.

  72. Nick Treat
    Nick Treat
    Mánuði síðan

    If you want to see if NP is real why not using negative mirror program

  73. Daniel ConR
    Daniel ConR
    Mánuði síðan

    wait askjfjaksjkfa please correct me if Im wrong, but are NP problems basically has no pattern in their difficulty/ number of steps (so we really cant decide if it is the most optimal solution ever)? and P problems are basically problems with confirmed most optimal solving sequence (fastest and low space)? and are NP hard problems just NP problem that we cant verify how good its solving sequence is (like in chess, we will never know how good is your move).

  74. Software Science
    Software Science
    Mánuði síðan

    I dislike the video because it does not introduce what P stands for and what NP stands for. For what I understand, P stands for Polynomial, and NP stands for Non Polynomial. At least hackerdashery should then explain what is polynomial in this case? Polynomial time? Polynomial equation? The absence of these stop me completing watching this video.

  75. Chris Smith
    Chris Smith
    Mánuði síðan

    this is one of the best computer-science related video ever

  76. Paul
    Mánuði síðan

    Formulae for chance?

  77. Jason Marshall
    Jason Marshall
    Mánuði síðan

    He said the answer but didn't realize it!i

  78. Whited Out
    Whited Out
    Mánuði síðan

    I once solved a hard sudoku without guessing...

  79. Martin From Strufve
    Martin From Strufve
    Mánuði síðan

    At the chess thing... We have build Deep Blue you know?.... 200 thousind solutions in 1 sec.

    1. Martin From Strufve
      Martin From Strufve
      6 dögum síðan

      @2Z Draw CAN happen 100% everytime, but it only happens when the players choose to move in a infinite specific place. Ofc depends on amount of pieces left. I agree with you on that point.

    2. 2Z
      9 dögum síðan

      @Martin From Strufve i said it badly, what i was meaning is that chess is a finite game, there is for sure a path where we would understand that white is 100% winner, or draw is 100% or even black but thats unlikely i think. Its like tic tac toe, a finite game where draw happen at 100%

    3. Martin From Strufve
      Martin From Strufve
      11 dögum síðan

      @2Z "we dont know the best path for 100% winrate" let me hang you up on this quote. Due to chess being a prohibited game in which sense, it has a non changing number of pieces, and an already stable amount of squares on the board, therefore calculation of x amount of moves can be memorized. Therefore, "the best way" is always re-calculated on the basis of the opponents move. This causes the machine to being able to calculate and differenciate its own moves parralled to the opponents.

    4. 2Z
      28 dögum síðan

      Deepblue would be extermineted by an algorithme that solved chess, chess is still unsolved, we dont know the best path for 100% winrate, Deepblue is just making very good guess, he dont know the perfect solution and this is what is about this kind of algorithme

  80. Gordon Pettus
    Gordon Pettus
    Mánuði síðan

    Solving Sudoku puzzles above size 9X9 is not difficult -- as long as you have a computer with a working memory which can store an array of (N**2) * 7. With that array, you can store all the information you need to be able to solve the puzzle. There are 4 primary subroutines which can identify solution numbers. There are two to four additional subroutines (depending on how you structure them) that will simplify the remaining puzzle of size 16X16. After simplification, the original 4 subroutines will solve the rest of the puzzle. For larger puzzles, the two to four subroutines would need to be adjusted to simplify larger n-ples. Why would you create a puzzle larger than 16X16 that would only be solved by a computer?