P vs. NP - An Introduction

P vs. NP is one of the greatest unsolved problems. Just what is it, and why is it so important?
Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Justin Chen, Brandon Chen, Elaine Chang, Zachary Greenberg
Twitter: / ubehavior
-
Extra Resources:
hackerdashery’s video: • P vs. NP and the Compu...
Wiki: en.wikipedia.org/wiki/P_versu...
Cook-Levin Theorem: en.wikipedia.org/wiki/Cook-Le...
SAT: en.wikipedia.org/wiki/Boolean...
P: en.wikipedia.org/wiki/P_(comp...)
NP: en.wikipedia.org/wiki/NP_(com...)
EXPTIME: en.wikipedia.org/wiki/EXPTIME
NP-complete problems: en.wikipedia.org/wiki/List_of...
Picture Credits:
commons.wikimedia.org/wiki/Fi... By Thomas Splettstoesser (www.scistyle.com) (Own work) [CC BY-SA 3.0 (creativecommons.org/licenses/...)], via Wikimedia Commons
cdn.vox-cdn.com/thumbor/PGO0k...

[@zoecarlibur]

The is the best explanation I ever heard on this topic.

[@zithfrg]

Could not agree more!

[@viniciusmartinez3537]

I'm a CS student, your videos are helping me paint an intuitive picture of some of the the topics in my courses' syllabus. I find that most books lack that key part of understanding, being able to create intuitive models. I subbed. Great work!

[@luke-da-duke]

The clarity with which you're able to explain such complex topics is unbelievable.

[@Joghurt2499]

I've just passed my last uni math class so now I can finally enjoy math again without having anxiety

[@diyasharma96]

Good lord. I was mesmerised by your ability to encapsulate an immensely complex subject in just a ten minute video. UNBELIEVABLE. Thank you!

[@irlserver42]

Nice! Keep up the quality work, I always look forward to your vids.

[@N7492]

Of the explanations of these complex topics, this is the best I've seen. Kudos to Cory.

[@Rannoch_]

You are the YT channel I wish I had started

[@Tee_eej]

Great channel and video! Your production value is extremely high! Keep it up

[@MrHatoi]

I knew it. The SAT is the hardest test in existence.

[@patrickzwangi4285]

Rectification: the hardest in NP

[@falquicao8331]

Best move in chess is much harder

[@hexa3389]

Laughs in the IMO

[@goat9629]

@@falquicao8331 the best atom to move to In football is even harder

[@paulmin82]

Amazing bro. Your videos are a work of art.

[@TheOscarJB]

thank you so much, I love your clean and simple animation, and also the elaboration

[@priyadarshianu]

finally! after 10 years of being introduced to this, I understand it. phewww....

[@bishwamayasahu4152]

Funny bro😂

[@vicmpen]

Hearing that some problems are impossible to solve, really got me down.

[@happy_thinking]

According to whom? Some people a century ago decided that flight was impossible, today we are going to space. Lots of solutions are actually very simple once you know the answer.

[@reicavera2235]

@@happy_thinking Its easy to prove the number of problems is bigger than the numbers of algorithms, which means there're problems with no solution.

[@happy_thinking]

@@reicavera2235 I am not sure what you are saying? New algorithms are created every day so even if some problems have no solution now it doesn't mean they won't tommorow. I mean how many people just one hundered yeard ago could imagine they could travel the world in 11 hours or talk and see people on the other end of the planet?

[@reicavera2235]

@@happy_thinking No. Its proven that undecidable problems exists and the halting problem is an example. Its impossible to make an algorithm decide if any algorithm will halt or loop forever because if such program exists we could make an algorithm that halt only if never halt(an contradiction). Short video about the halting problem : m.kzbin.info/www/bejne/o5LGfpKDqbiSrZY

[@happy_thinking]

@@reicavera2235 I will assume that is correct. My point was more that with new technology come new solutions. For example it was impossible a hunded years ago to get in one hour from Europe to America because we didn't have planes. Today we do. So while this problem has no solution now it doesn't mean it won't forever.(Or maybe it will)

[@petermc164]

This description is gold, please make more videos!!!

[@DudeWhoSaysDeez]

Out of the 7 problems (that if you solve them you get a million dollars), i find p vs np to be the most interesting and most practical one that we should keep investigating

[@schilduin]

It's actually the most abstract one. Even if it is solved (and it may be that there is a proof that it's unsolvable), we probably won't be able to make a lot of use of the solution in real world applications.

[@tzakl5556]

The Rienman Hypothesis is also quite interesting

[@GustavoBordieri]

Great stuff, keep up the good work!

[@santiagolicea3814]

What a great explanation man, this is great great content. Thank you so much!!

[@shubhamshinde3593]

I wish you were more active :( Your work is amazing!!

[@omerfc1]

Yet another great video!

[@davidjpfeiffer]

Keep up the great work! Your videos are great!

[@shivmahabeer9450]

Wonderful work! Thank you.

[@011azr]

Whoa, this is so clear. Thanks!

[@lukafarkas420]

great visual explanation, good job m8

[@StoneColdProfessor]

Less than 3 seconds in and you've got a new subscriber. :)

[@kevinpfeil4309]

This is insane. Thank you

[@Speak4Yourself2]

Outstanding video. Thanks a lot!

[@tomstaite6487]

Great introduction, thanks!

[@MariaFlorenciay]

Very nice tutorial!! well done!

[@faryedeltayesh3352]

Excellent job

[@nainakoujala4545]

This was an amazing video thank you sm!!

[@TheSaa94]

amazing video, thank you!!

[@ahasdasetodu6304]

What you described under hamiltonian path is actually an euler path, hamiltonian is such that every vertex (in this case city) is visited exactly once

[@want-diversecontent3887]

My method to solve jigsaw puzzles is to solve the corners first, then the edges, then the harder problem: the centers

[@Kirmeins]

Great... now try that with a bunch of pieces that *may or may not* belong to the same puzzle in the same amount of time. Imagine just one piece doesn't belong to the puzzle - you *couldn't proof that* until that one piece is the last that's missing. That's a lot of time you just wasted - if only you had a faster method to decide if a piece belongs to the puzzle or not - without knowing which puzzle you're even looking at of course! ;)

[@blaisereints9488]

Great Video. Very helpful

[@ritulritul2312]

really cool animations ! :D

[@UUTUUH]

This is amazing!

[@PvblivsAelivs]

If P were found to be equal to NP, it would cripple _all_ of cryptography. Most cryptographic algorithms rely on a secret key. But if finding that key were made no more difficult than checking to see if it worked, only the one-time pad would be spared.

[@Stl71]

But first of all, you would get the prize of 1 mil. dollars.

[@beclops]

@@Stl71 The prize should be way more. You could revolutionize almost every industry with this discovery.

[@tmahad5447]

I am currently working on the SAT problem and its polynomial solution. So far i have made a huge progress

[@oliver_siegel]

Great video!

[@NightyWriter]

At 3m36 there seems to be a reference to TED video/talk. Has anyone found this video? Thanks!

[@pycat141]

Thank You, sir!

[@temisegun8631]

thank you thank you thank you!!!!

[@huzaifafarooq9130]

Awesome video

[@aryaparvizi8755]

great video.

[@albertnoub371]

thanks your video has been productive

[@the_anuragsrivastava]

Nice explanation... thank you

[@AmirAli-gv7kn]

So, exptime is basically NP Hard?

[@stapler942]

What if Deep Thought could solve the Ultimate Question in polynomial time, but the answer can't be verified in less than exponential time without knowing the question? Does P become a superset of NP? Or does the universe simply get replaced by something more bizarre and inexplicable?

[@addisalemwudu275]

what does it mean by polynomial time algorithm?

[@hkpatnaik]

Best explanation of Big O in the whole you tube universe

[@onurcanisler]

*HATS OFF.*

[@ravindrawiguna8681]

If problems that exist in p is also in np, and everything that exits in np can be turned into SAT problem, then problem in p can be turned into SAT problem (p =np=sat?) Therefore we can easly solve the problem and verified it right? Idk man, the logic just stumble upon me while watching the video. So like if that the case, if we can somehow generalize the algorithm that we use to solve the P turned SAT problem, maybe it can work on other np problem?

[@yourkingdomcomeyourwillbedone]

Couldn't we create an algorithm for solving jigsaw puzzles by mimicking the way that we naturally solve them? i.e - piecing together individual parts to form 'chunks' until those 'chunks' resemble larger pieces of the complete picture?

[@yassineinsta7731]

1. Is there a place without time? 2. Is there a verb without a tense? 3. And if there was a time and we did something, does this mean that we did something without time? 4. If we did not do anything in a timeless place, does this mean that we did not do anything in a time?

[@csanadtemesvari9251]

0:56 a number's GCD? Hello?

[@matevzvidovic6708]

Yay! You're back😁

[@skyatianlan2356]

Thanks, subscribed

[@noli-timere-crede-tantum]

Sounds like my parents explaining stuff to me in my childhood: makes the topic at hand sound profoundly complicated, but keeps using the words, "we just don't know."

[@ahmedifhaam7266]

what do you mean by poly time

[@WorldOfPersianDoc]

Is game of life in NP? CAuse at 2:23 I saw you put it in P.

[@prashantshinde5083]

Keep up . You deserve more suscribers. Such a boring concept and you made it so much interesting.

[@msbalzgiip7365]

6:30 The game of checkers has been already solved by computers. Is it still classified as being in the EXPTIME category?

[@ir2001]

MsBal ZgIip Solving it from scratch is considered to be EXPTIME but once we have the solution it's simply CONSTANT TIME because we can use hashing

[@msbalzgiip7365]

@@ir2001 Thank you for explaining it!

[@anilmudgal4405]

good job

[@patrickperot6296]

Aren't NPs just a combination of Ps (whether a basic combination or a complex one)?

[@quosswimblik4489]

My understanding of P vs NP say your computer has one core that does 1 operation per cycle and you could do 1000000000 of these operations per second. now say you want to say do an algorithm on two numbers. Lets say your algorithm took 12 of your compute operations per digit as your algorithm operated though all the digits. Then to find the maximum amount of compute operations your code is running up, simplify the Issue and say that 12 is flat because it doesn’t increase with digit size. As digit size of the inputs goes up the complexity of the problem is the digit length of the two inputs or in other words O Log[n] in terms of its complexity with n being your input number and Log[n] being your digit length. Such an algorithm can handle big inputs on a modern computer and spit out a result very quickly. How ever if a problem was O n or O n^2 and n was your number of inputs. then on a modern computer it would be able to handle about 10 000 to 10000000 inputs this is what is meant by P time. Solving sudoku for any given grid size is in NP complete time this means that if you could work with all possible algorithms at once you would find a P time solution but you would possibly need this type of theoretical machine to achieve it that’s the real question can we find a universal P time solution to such problems or are we stuck with exp time solutions like O 2^n. Note. saying it's quick to verify a correct solution is the same thing as the nondeterministic P time computer being able to determine a P time solution.

[@rocky_wang]

Is getting full score in SAT (Scholastic Assessment Test) an SAT (as defined in this video) problem?

[@nrwchd]

[sat]isfiability problem, math like take three letters like sine, cosine, and tangent became sin, cos, and tan.

[@elliottesponda2802]

The halting problem is semi-decidable. The complement of the halting problem is udecidable.

[@eclipse-xl4ze]

nice video I subbed

[@kiarrasierra7221]

I agree with this I am actually not a mathematical person what so ever but its taken me 20 minutes of research to understand this lol. But i think that if you had a "puzzle" to complete but didn't know anything about it to say that you could compete it is a past theory. I think in order to actually solve this question you would have to run analysis on every single thing in existence put different problems in different situations compare them against everything in existence and have infinite problem solving solutions to actually have an answer to P versus NP. I think if you focused on that you wouldn't have to worry about the past of knowing of this puzzle could be complete or not, because you would have your answer (with one of many tools that would give your problem the correct answer) in the puzzle situation you would have an infinite case of puzzles being solved by humans that would be uploaded to a software that would predict the out come due to the pattern of placing the puzzle, plus a scanner to scan every piece of puzzle to determine if all the pieces would match and make a puzzle to begin with. Look to the future before determining the past. But this is just one scenario, every thing in existence would have to go through that analysis.

[@user-ne7vn6xc1f]

مشكورة حبيبتي

[@toothfairy5352]

What is SAT?

[@arghyamitra3281]

jst awsmmmmm

[@misstori1437]

Count the number of pieces in direct reference to the number it is supposed to have

[@adityamishra7711]

Offcourse, it should have that many pieces, the question is about the algorithm, which piece to take first, how or where to put.... which to take next.. irrespective of the picture the no. of pieces depict when solved.... So, you finally kinda believe that its impossible to join the pieces correctly such that it matches the picture without looking at the picture in the first place... But that's just a belief, maybe there is way after all... till today no one has found any such way.... The million dollar question thus simply asks if there even is a way... If yes then , p = np Else, p != np So if you can solves any puzzle without looking at the picture or the part of the picture each piece depict , i.e. only by the shape of the pieces then .... congrats you become a legend... But i hope you can see how a majority of the greatest minds in computer science believe the other way round... The frustrating thing is that our current mathematical tools are just not sufficient to prove it rigorously.....

[@want-diversecontent3887]

What is EXPSPACE?

[@ashishshinde7996]

Hi Cory and others reading this, Please see Hacker Dashery says Efficient Markets is NP complexity and if 1 class collapses others can be solved. Now I have a solution for EM=P , my algorithm is RAAC (Business Model atm) but if you look at it objectively it is an algorithm which will help us lay foundations for Unified Market. My angle to P=NP is economics right now as economic freedom for all entities is my struggle. In complexity zoo of commodities for wealth generation, I have added a new, Physical robots as they are a passive wealth generation tool. Please help also see the concept of positive feedback loop. RAAC is same with increased complexity. Regards Ashish

[@artvanderschlut7205]

What's with the melting turd penguin graphic?

[@gplor5259]

This video is so eazzzzyyy

[@souldigger4157]

Thank you for the great explanation

[@user-cf3vi9kf7v]

If N=1 P=NP

[@georgiepentch]

Or if P=0

[@misnik1986]

you have just one one million dollars hhh

[@cyrushyram5673]

Its a yes or no question

[@dscmtr686]

These are sets. Why this answer is liked so much xd it's stupid to even joke like that.

[@TheGargalon]

How can you mathematically prove/disprove something as abstract as P=NP? What does the equation even mean? Is there complexity hidden behind the P and NP letters? I'm no math expert, just curious.

[@SmileyMPV]

saltychicken1 The question is formally defined in mathematical terms with the help of turing machines.

[@theultimatereductionist7592]

Proving P=NP would involve finding an algorithm that solves all problems in NP in polynomial time in N, the size of the problem. Proving P!=NP would imply proving no such algorithm could exist.

[@avianbirds]

P and NP are mathematical sets, not algebraic variables.

[@Yamikaiba123]

SAT does not necessarily exist, I feel. Can you not have some NP problems that are irreconcilable with each other and hence cannot be solved by a common algorithm?

[@zaidsserubogo261]

Where easiness becomes difficult and vise- vasa; It also bothers my mind if one starts addressing P verses NP problem from secondary point of view (which lands us into complication but not complexity) but not from the first principle of computer complexity. There goes..... 1-are there problems which a computer can solve and those which it can not solve as well as verify the answer? 2- how do we get to the answer for the first question? computers solve real and imaginary problems logically and mathematically. 3- mathematical problems fall under P and logical problems fall under NP. 4- what about the complexity of logical language in evaluating and deciding on real and imaginary problems? 5- the answer to logical complexity help us know the type of problems solvable and verifiable by a Computer since logical systems reduce to mathematical systems and mathematical systems are produced by logical systems 6-can this math-logical reduction and production relation run in polynomial time? 7- the rest goes as bra bra bra justifications where this complications are simplified inform of complexity . . . Etc

[@dscmtr686]

But wait. SAT is most common problem for using reductions. Sombody (you mentioned) proved that SAT is NP-Complete problem, that means at least as hard as all problems in NP class. However in reductions, you are reducing FROM SAT to other problem, which we want to prove is NP-complete. That means other problem is NOT EASIER than SAT. So why idea that SAT is the hardest one? Where did you find this information? I don't understand.

[@fungus4898]

When you are studying calculus and python with this p vs np problem your life will become a problem.

[@juanlinde9028]

+ 1 for Sacred Heart reference

"Before we get too crazy..". Too late.

[@gerry7457]

Just a shot in the dark, sort of speak. Using sound waves at the atomic level at different temps to verify different answers/solutions. Meaning if the tone/wave is duplicated and returns without any variances it would conclude/confirm the input is correct. Example; If you want to break a wine glass with a pitch voice; you must replicate the same tone the wine glass resonates. Sound waves can be measured at any levels - electro-magnetic. Anything repeating can be measure in terms of frequency. I'm losing myself here but it would be constant in a construct that is self contained in controlled environment. Eventually, a day will come it will be the inventors, philosophers, the out box thinker will be the genius' as everything will reversed engineered with the "idea". That poses another problem with that kind of power. My favorite phrase is; You cannot have something out nothing or nothing out something.

[@bakedutah8411]

1:51 Why exactly is jigsaw O(4^n . n!) and not just O(n!) ?

[@TheSpongbob27]

rotating a piece

[@bakedutah8411]

13LAk_vviDoW, you’re right. Thx. I’m probably doing overly simple jigsaw puzzles 😬

[@jeremiahmullikin]

An algorithm for intuition can fix this.

[@yourkingdomcomeyourwillbedone]

By definition that would be impossible.

[@thegnat2955]

Jigsaw puzzles are in P; start with a corner piece and iteratively find the next piece by running through all the pieces and finding whether one fits in some orientation. If none do, the puzzle is impossible. This is quadratic time. Aside from that, nice explanation.

[@docrun3516]

Nah lets say u find the piece. Then again you would have to find the next piece in n-1 times and so on. The worst case would always be the last piece found if im thinking correctly, thr worst case scenario is O(n!) Or sth like that, which gets huge

[@WhoForgot2Flush]

That sounds like an exponentiation function to me....

[@aamodvardhanpandey]

hmm, use the doctor's tardis in ur vids?

[@Hedning1390]

Someone wasn't very smart when they defined and named P and NP problems. Basically what the venn diagrams are saying is that all P problems are also NP problems, so then saying that a problem is NP tells you pretty much nothing. Instead to convey information you need to say that a problem is "not P". However this is not how the term is used. Saying that a problem is NP is every time I've heard it meant to say that it is hard, or not p. This is especially confusing because it is easy to think n stands for "non" as in "non-p" which is the opposite of the definition.

[@shouryap]

The name comes from Non-deterministic Turing Machines. The definition in the video is not the "first" definition of NP.

[@REDDEADANDGTACLUB]

I think you've confused Hamiltonian path with Euler's path.

[@darrenb]

REDDEADANDGTACLUB I clocked that too, Euler Tours (paths and cycles) being the subject of my BSc thesis; Hamiltonian Path problem is about vertex visitation once and not specifically about edge traversal once, although that emerges by necessity

[@JiffyDealer]

This sounds like problems are best described as a spectrum.

[@RipleySawzen]

1:51 There's no way a puzzle is O(4^n*n!). I found an easy upper limit of 6n^2.

[@alchemistsnightmare]

[@einemailadressenbesitzerei8816]

For me its pretty obvious the P unequals NP. Why is it so hard to prove, that there will never be an Algorithm that can solve a NP-complete Problem in polinonmial time? I mean it seams pretty obvious. All problems one thought are in NP and were solved later people found out that they are actually problems from P and not NP. I mean if i have chess and want to completly solve it it is impossible to skip the paths in the tree without any approximation i have to check all the paths in the tree, so there will never be a solution with less complexity except i use Heuristics and Approximations(NNs), evaluation functions, etc. How can you prove that there will never be an Algorithm that can solve an NP-complete Problem in Polinomial time? I mean its like proving that there is no way that i come from O(2^n*n) to O(n^c) , c= constant, n=number of instances in problem here in example for TSP.

[@shortcutDJ]

aaaaaaaaaaaaaaaaaaaand subscribed!

[@RetroGamingClashOfClans]

I can prove P = NP as I have solved the traveling salesman problem JK but I'm working on it

[@einemailadressenbesitzerei8816]

i dont think that there is an algorithm of any NP-complete problem that brakes down complexity to polinominal time without any approximation or heuristic. I think you should focus on how to prove that there will never be an algorithm to solve any NP-Problem in polinomiel time.

[@northamericalife3769]

me too: vixra.org/abs/1805.0399

[@einemailadressenbesitzerei8816]

@@northamericalife3769 why not publish it on arxiv.org?

[@northamericalife3769]

@@einemailadressenbesitzerei8816 They don't publish if you don't work at any University or similar institution

[@MrMichaelsu]

I made a 3x3 sodoku from scratch and it was super easy.