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!
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
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.
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 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?
@@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.ua-cam.com/video/macM_MtS_w4/v-deo.html
@@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)
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.
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! ;)
Okay so, there is a slight misconception about the Cook-Levin theorem here. This theorem states that SAT is NP-complete, which means it belongs to NP and is at least as hard as every other problem in NP. That doesn't mean it is "the hardest problem in NP", in fact it says nothing about how easy it is to come up with an algorithm to solve it. Rather what it does say is that every problem in NP can be polynomially reduced to SAT (read translated to) and be solved via that route. It is a subtle detail but an important one for consistency!
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."
The phrase “huge swathes of problems we once thought were hard would suddenly be easy,” suggests that P cannot be equal to NP just because the problems are not easy. That’s not a proof, but a reason for conjecture. The concern would be if proving “P not equal to NP” is an NP problem or an XP (EXPSPACE) problem, since a proof is essentially a verification.
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?
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.
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?
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.
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.
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
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.
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?
In the future, you could use the word "inside" instead of "in" when you're talking about a location/classification. For example, say "Sorting is inside of P" instead of saying "Sorting is in P", which obviously could be confusing.
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.
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
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.
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
You have a mistake, it seems to me, under 4 minutes in. Checking whether or not the puzzle is solved is not done in polynomial time. It's in linear time. Time to check = (time to verify a piece's connections)(number of pieces in the puzzle) You showed this earlier in the video. Though, maybe linear time is a type of polynomial time?
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?
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.
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.
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
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.....
If SAT being easy is such a difficult question, then why don't we feed instances of SAT to the masses. Release a game that boils down to SAT, even better: Do it with a VIDEO GAME! Oh wait, that has already been done with almost all games. But I mean in a more direct way, just packaged slightly so that it is not "(a+b)*(!a+b) Is this solvable?" but also not in a way that it is so highly packaged. Maybe throwing more multiple engaged minds at the problem will lead to some insights, or at least give us a small hint.
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.
The is the best explanation I ever heard on this topic.
Could not agree more!
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!
The clarity with which you're able to explain such complex topics is unbelievable.
I've just passed my last uni math class so now I can finally enjoy math again without having anxiety
Good lord. I was mesmerised by your ability to encapsulate an immensely complex subject in just a ten minute video. UNBELIEVABLE. Thank you!
finally! after 10 years of being introduced to this, I understand it. phewww....
Funny bro😂
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
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.
The Rienman Hypothesis is also quite interesting
Hearing that some problems are impossible to solve, really got me down.
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.
@@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.
@@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?
@@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.ua-cam.com/video/macM_MtS_w4/v-deo.html
@@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)
I knew it.
The SAT is the hardest test in existence.
Rectification: the hardest in NP
Best move in chess is much harder
Laughs in the IMO
@@falquicao8331 the best atom to move to In football is even harder
Nice! Keep up the quality work, I always look forward to your vids.
Of the explanations of these complex topics, this is the best I've seen. Kudos to Cory.
Amazing bro. Your videos are a work of art.
You are the YT channel I wish I had started
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.
But first of all, you would get the prize of 1 mil. dollars.
@@Stl71 The prize should be way more. You could revolutionize almost every industry with this discovery.
Yes, it is going to be P=NP.
That is also true of Quantum Computers, so we should be working around that anyway
My method to solve jigsaw puzzles is to solve the corners first, then the edges, then the harder problem: the centers
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! ;)
Okay so, there is a slight misconception about the Cook-Levin theorem here. This theorem states that SAT is NP-complete, which means it belongs to NP and is at least as hard as every other problem in NP. That doesn't mean it is "the hardest problem in NP", in fact it says nothing about how easy it is to come up with an algorithm to solve it. Rather what it does say is that every problem in NP can be polynomially reduced to SAT (read translated to) and be solved via that route. It is a subtle detail but an important one for consistency!
I am currently working on the SAT problem and its polynomial solution. So far i have made a huge progress
Great channel and video! Your production value is extremely high! Keep it up
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
This description is gold, please make more videos!!!
Less than 3 seconds in and you've got a new subscriber. :)
I wish you were more active :( Your work is amazing!!
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."
Best explanation of Big O in the whole you tube universe
thank you so much, I love your clean and simple animation, and also the elaboration
The phrase “huge swathes of problems we once thought were hard would suddenly be easy,” suggests that P cannot be equal to NP just because the problems are not easy. That’s not a proof, but a reason for conjecture. The concern would be if proving “P not equal to NP” is an NP problem or an XP (EXPSPACE) problem, since a proof is essentially a verification.
This is insane. Thank you
great visual explanation, good job m8
What a great explanation man, this is great great content. Thank you so much!!
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?
Outstanding video. Thanks a lot!
Whoa, this is so clear. Thanks!
Best explanation video
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.
مشكورة حبيبتي
Wonderful work! Thank you.
This was an amazing video thank you sm!!
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?
Thank You, sir!
6:30 The game of checkers has been already solved by computers. Is it still classified as being in the EXPTIME category?
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
@@ir2001 Thank you for explaining it!
Very nice tutorial!! well done!
Great stuff, keep up the good work!
So, exptime is basically NP Hard?
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.
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.
Excellent job
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
Keep up . You deserve more suscribers. Such a boring concept and you made it so much interesting.
Great introduction, thanks!
Awesome video
Yet another great video!
Keep up the great work! Your videos are great!
*HATS OFF.*
Great video!
great video.
Nice explanation... thank you
Aren't NPs just a combination of Ps (whether a basic combination or a complex one)?
The halting problem is semi-decidable. The complement of the halting problem is udecidable.
When you are studying calculus and python with this p vs np problem your life will become a problem.
amazing video, thank you!!
what does it mean by polynomial time algorithm?
Is getting full score in SAT (Scholastic Assessment Test) an SAT (as defined in this video) problem?
[sat]isfiability problem, math like take three letters like sine, cosine, and tangent became sin, cos, and tan.
I can prove P = NP as I have solved the traveling salesman problem
JK but I'm working on it
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.
me too: vixra.org/abs/1805.0399
@@northamericalife3769 why not publish it on arxiv.org?
@@einemailadressenbesitzerei8816 They don't publish if you don't work at any University or similar institution
Great Video. Very helpful
Is game of life in NP? CAuse at 2:23 I saw you put it in P.
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?
In the future, you could use the word "inside" instead of "in" when you're talking about a location/classification.
For example, say "Sorting is inside of P" instead of saying "Sorting is in P", which obviously could be confusing.
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.
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
That sounds like an exponentiation function to me....
thank you thank you thank you!!!!
really cool animations ! :D
thanks your video has been productive
An algorithm for intuition can fix this.
By definition that would be impossible.
Why would solving a Rubik's cube be a np problem?
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.
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
At 3m36 there seems to be a reference to TED video/talk. Has anyone found this video? Thanks!
You have a mistake, it seems to me, under 4 minutes in.
Checking whether or not the puzzle is solved is not done in polynomial time. It's in linear time.
Time to check = (time to verify a piece's connections)(number of pieces in the puzzle)
You showed this earlier in the video.
Though, maybe linear time is a type of polynomial time?
Linear functions are polynomial, so linear time is polynomial time
This is amazing!
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?
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.
saltychicken1 The question is formally defined in mathematical terms with the help of turing machines.
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.
P and NP are mathematical sets, not algebraic variables.
"Before we get too crazy..". Too late.
what do you mean by poly time
I think you've confused Hamiltonian path with Euler's path.
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
+ 1 for Sacred Heart reference
Thanks, subscribed
This sounds like problems are best described as a spectrum.
0:56 a number's GCD? Hello?
What is SAT?
good job
Count the number of pieces in direct reference to the number it is supposed to have
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.....
jst awsmmmmm
If SAT being easy is such a difficult question, then why don't we feed instances of SAT to the masses.
Release a game that boils down to SAT, even better: Do it with a VIDEO GAME!
Oh wait, that has already been done with almost all games.
But I mean in a more direct way, just packaged slightly so that it is not "(a+b)*(!a+b) Is this solvable?" but also not in a way that it is so highly packaged.
Maybe throwing more multiple engaged minds at the problem will lead to some insights, or at least give us a small hint.
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.
The name comes from Non-deterministic Turing Machines. The definition in the video is not the "first" definition of NP.
7:26 "if P Diddy"
1:51 There's no way a puzzle is O(4^n*n!). I found an easy upper limit of 6n^2.
Lets say i have 2 apples
Therefore P=NP
My gosh. So this is what happens when I play Ticket to Ride.
If N=1
P=NP
Or if P=0
you have just one one million dollars hhh
Its a yes or no question
These are sets. Why this answer is liked so much xd it's stupid to even joke like that.
1:51 Why exactly is jigsaw O(4^n . n!) and not just O(n!) ?
rotating a piece
13LAk_vviDoW, you’re right. Thx. I’m probably doing overly simple jigsaw puzzles 😬
Mein hu Don mein hu don
What is EXPSPACE?