the very important part of this is that some problems that thought to be NP at the beginning was later discovered as P. That's why we ask is there a chance that all NP are actually P and we simply approach them wrong way.
We do approach the issue from all angles, some people are still working on particular problems. The reasons "does P equal NP?" is a very natural question is that some problems are NP-complete, and showing only one of them to be P is really the same thing as showing P=NP.
@@chunkyMunky329 by definition, a language L is NP-Complete if there exists a polynomial time mapping reduction from every language in NP to the language L. Mapping reductions are transitive, meaning that if one NP complete language was shown to be in P, then not only would NP-complete = P, but NP=P.
@@stoopidpants explanation for the layman. formal definitions are needed if you need to prove, via polynomial-time reductions, that a given problem belongs to a particular class.
@@pussiestroker Yes, obviously. But what I was saying is he explained a concept that's so fascinating it took me a REALLY long time to understand. This is just an extremely good example of what I call the "Feynman Effect" wherein a person has taken a complex topic and made it perfectly accessible, on a lay level, to just about anyone willing to listen for 5 minutes. Even after hearing it a few times I still can't explain it as well as he does; no even friggen close.
It's super interesting stuff you learn in CS curriculum. If tomorrow it was discovered P=NP, computers overnight would become super computers that would be able to do unimaginable things, solving world problems including a possible cure for cancer (the idea is to make an algorithm that could quickly compute customized treatments for individual patients with cancer, diabetes, AIDS, etc.) The gut feeling though is that P != NP, but there is no formal proof of that yet.
@@jaftem2x P=NP doesn't mean automatically that computers become super computers. Most problem that we usually talk about which are in P can be solved "quickly", but we can easily find problems in P that solving them will take so long that one life time will not be enough. If we do manage to prove that P=NP, there is a good chance that the hard problems in NP are actually in the part of P which take very long time to solve. We do, however, have many tools to "almost" solve problems in a short amount of time, for example, using all sorts of heuristics and probabilistic methods. If our goal is to solve hard problems quickly, this is a much better method, than trying to prove that P=NP.
@@eofirdavid "but we can easily find problems in P that solving them will take so long that one life time will not be enough" I assume this would be in the cases where, as Scott discussed, the exponent of the polynomial function is large?
@@synchronium24 Yes. The degree of the polynomial is quite important when we speak about running time. As Scott said, linear, quadratic, and in general small exponents are "fast". On the other hand, if we have a problem which is solved in n^10 time and even for a very small input size n=10, we will need 10^10 computer actions to solve it. If each of these actions in such an algorithm takes 1/1000 of a second, then it will take more than 100 days to finish it. In most algorithms, the input size is much larger than n=10, to the point that in some of these problems even linear and quadratic is too much.
What I find so interesting about theoretical computer science, is that many of these problems are fairly easy to understand. Stuff like sorting numbers or coloring maps. Yet when you analyse their complexity, you find interesting relations such as that some problems can be reduced to other problems, meaning that there are sets of problems that are essentially equivalent. You can take the algorithm that solves one of those problems and use it to solve any of the other in the same set by transforming the input and the result. I find it fascinating that problems can be "ranked" by their difficulty and what the landscape of algorithmically solvable problems looks like.
The way it's described here it sounds like P=NP means: Does any hard to compute algorithm who's solutions can be checked easily, actually have an alternative easy to compute algorithm, that we just haven't found yet? Is that right?
Pretty much yes. A different way of viewing the class of NP is like this: We have a problem where we can try one possible solution out of many in a small amount of time. But to always find the correct solution we need to check alot of possible solutions. If P = NP holds, then we will always check the correct solution first. So to speak we are always lucky. Lets say we want to solve a sudoku where 78 spaces are already filled and we know the last 3 spaces contain 1,2 or 3. A possible Solution contains 3 numbers that might fit the board but probably dont comply with the rules. So we have to check (1,2,3),(2,1,3),(3,1,2),(1,3,2),(2,3,1),(3,2,1). If P = NP we can find a way of sorting our possible solutions in a way that we just try the correct one. And that is without actually solving the sudoku. If this leaves you suprised: "But wait that is all you have to do in Sudoku, find the correct set of numbers". Then you know why most Computer scientists say it cant be P = NP.
@@Schnorzel1337 Adjust the environment so the physics of the environment will dictate that the correct answer always rises to the top instead of interacting directly with the "solutions". In a sense, make laws for your program that dictate certain influences should take hold where correct answers are favored and incorrect answers are demerited. Do this to an extreme degree until you can reach certainty, shift the need for probabilistic thinking one floor up so you can deal with the program in a more sleek manner.This is different from machine learning where you recognize patterns because this is more of you directly establishing laws for your environment. Where do laws arise from?
It's not that hard to understand really, there was just way too little context if this is totally new to you. If it was like a 1 hour course with some drawings and more examples to guide it, I think most ppl would be able to understand what P and NP problems are, and what the question P=NP? means. During my CS courses this was not the first lesson of theoretical CS, it had a few hours of lead in lets say. What can be a lot harder/impossible, is proving that some given problem/solution is P or NP.
@@spungoflex3285 Very abstract, if you play a computer game for the first time you got so many options and ways to achieve victory that you are confused and take forever to complete it. But if the equation P = NP holds, then every game comes with a book that 100% details how the game can be beaten, you still have to play the game, but you know exactly how.
When I was working I never had the time to think about whether P = NP has too busy thinking about the latest project end date or whether T equals chips.
It's not really that hard. Imagine a simple algorithm, it has an input and an output. The algorithm has a set of operations to do on the input to get the output, and we can count them. We then say that an algorithm is of complexity O(n) if, with an input of size n (you can think of an array of n elements for simplicity) we need to do n operations to get the output. We call P the set of problems of complexity O(n^a), where a is a natural number. These are problems that we can solve easily with our current computer, even with huge inputs. We call instead NP problems that are of complexity O(2^n) or similar, basically where n Is the exponent. This means that for every new element you have in input, the number of operations you need to do at least doubles. You can see where the problem is. So why are they asking if P=NP? Because if we find a way to solve an NP-complete problem (meaning all other NP problems can be reduced to that) in polinomial time, then we can solve all NP problems in polinomial time and it would be a revolution for computer science and mathematics
@@AL3X2011 well yeah that's my background so i probably took some things for granted, but this channel talks pretty advanced topics so i hope people know at least the basics of cs
@@AL3X2011 you mentioned that most don't know what an array is...I also pondered over what "0(n)" could mean, tried to picture in my mind what "n elements" might look like, wondered where the "a" appeared from in the previous "0(n)" thing, and then we learned that NP describes "problems of complexity 0(2^n) or similar" apparently, which brought me back to ponder over what "0(n)" means...🤷♂️
@@adamdaly4847 imagine a list of n numbers, okay that's your array. Imagine i write a program that sums all those numbers, well i would have to cycle through the array adding the number to the sum. This costs O(n), meaning i need to visit all numbers of the array once to get my result. If i needed to visit them all twice, the cost would be O(2*n). It's pretty hard to explain it to someone with no cs background whatsoever though
If say for a 4 colour sudoku you make a grid for each of the 10 4 colour combinations with 2 1’s for every row subgrid and column representing a pair. Then if you sweep your possible 1’s there will always be at least 1 of the 1’s that is invalid. It's like having a p time oracal where every time you sweep the 1’s at least 1 of the 1’s can be crossed off.
This is one of the 7 Millenium Prize Problems outstanding as of 2000. Solving or in (all) most cases, proving, the idea true or false will net you USD$1 million. Only one of the 7 has been solved, the Poincaré Conjecture, which dealt with hyperspheres. It was solved in 2006 by Russian mathematician Grigori Perelman, who refused the $1 million cash prize. Fascinating.
Graph coloring problem is solved recently last in 2-3 years turns out any graph can be colored with Minimum 4 colors. Solution was very inelegant it was brute force approach but meh we got the answer
Wait he says 2-3% odds that P = NP right after saying if he were a physicist he would declare it so that N not = P. The 5-sigma standard is highly offended.
Well if you look at concrete trials that have been made to transform NP problems into P solutions, so far all of them failed so we easily get to 5-sigma standard. Maybe a bit harsh to physicists though.
@@SymEof fair point. Probably some fairly deep philosophy of science happening comparing natural experiments with formal computational "experiments." It's still bogus imo to connect 2-3% odds to absolute certainty for a physicist.
@@SymEof there are NP problems that can be solved by reducing the problem to another solution that exist in P. The issue is that we need to prove that every NP problem can be solved that way, it's a math demonstration, and they are very complex and long to do on such argument. there is a prize for one that can prove it, of several milions $.
@@SymEof well, 5-sigma is more of an experimental probability of significance though. It doesnt really apply to mathematical proofs. Also, you cant have a proper probability rating for whether a conjecture is true or not. You can have a confidence rating (which is what that 3% estimate would be) but its not quite the same thing as a probability in the experimental sense. Also, there are many NP problems that have been reduced to P, but there are also many NP problems that have NOT be reduced to P. The NP problems that have been reduced to P are obviously the ones where it was possible. But any NP problem that cannot be reduced to P could very well be impossible to reduce which is why it hasnt been done yet. Actually, more on that, there is a specific type of NP problem that has shown up many times in many different fields and problems that has not yet been reduced to P, and its conjectured by many that it is impossible to reduce it to P. This may actually be the key to solving the P = NP conjecture but nobody has devised a proof yet so that remains to be seen.
It is P=NP. 100%. I have the polynomial solution for the SAT NP complete problem. I don't know where or how to publicize my finding in magazines. Any help in this regard is highly appreciated.
P = NP P/P = NP/P 1 = N 1 = true Since N stands for "Not" the "not" part of this problem is true (N=1). So since the ' "Not" polynomial' part is true, P != NP
What’s the difference between physicists and mathematicians you ask? “If we were physicists we would just declare that P =/= NP as a law of nature and give ourselves Nobel prizes for it's discovery, and if later it turned out that we were wrong we would just give ourselves more Nobel prizes.” 😂😂😂
Can you please do a long-form interview with GPT-3? Its responses depend heavily on the questions asked and I think you could extract some fascinating answers from it.
Interesting, freelance predictive AI in the late 90s using methods like Bayesian probability, hidden Markov models, deterministic selection, etc... Did a major multi year project to predict stock dumps. Worst years of my life. It is extremely interesting to hear about the direction classes and education has take in cs. I still have a intrest in AI but wouldnt trade the life I have now. Work with my hands, designing and building things others use, and the connection this process gives me with my family is so rewarding. -David Dennis
@@pawanbhatt314 you didn't see it? He showed me his proof and I checked it. It's legit, just a little too long to fit in a RUclips comment but P=NP does in fact hold :)
No, that would by definition take an exponential amount of time on a deterministic turing machine. On a non-deterministic turing machine, yes. Infact, that is how you go about proving that a problem is in NP: you prove a solution can be checked in a polynomial time (known as the certificate) then a non deterministic turing machine can simply non deterministically check every possible solution (in polynomial time)
P=NP. is such an elementary question if you look at 1:58 you can see how annoyed Lex is that he took 2 minutes to explain something so simple. Basically to verify a question you have to solve the question, because you tend to just redefine in maths. But is this ALWAYS true? Is verifying always just doing the solving again. I always get annoyed by these questions, because instead of solving the million dollar question people just find ways of explaining it. I truly think some people like to make things "complex"
If you are talking about Neural networks I can assure you, no neural network can ever prove that P =NP. Think about this way. There is no known algorithm specificly designed for a problem that breaks open the NP part. And now you throw that all in the wind and use a generic method to solve that? Very very unlikely.
@@Schnorzel1337 www.nature.com/articles/d41586-020-03348-4 Honestly wondering what you think of this result. I don't have a ton of context but I have understood protein folding to be one of the most classic examples of an NP problem, is that not the case?
@@Deez-Master Very interesting for that field of reasearch. But unless you can prove that you can understand the folding of every possible protein you are not one step closer to P = NP. In my experience it is often easy to find a NP problem for which some inputs are trivial to solve. Lets say you want to calculate a solution for the Traveling Salesman Problem, which asks for a minimal tour through n different cities and returning back to the starting city. This problem is NP-hard. But if all cities lie on a grid or a structure of some sort, it becomes trivial for any number of cities. The general case is what breaks the argument. Excursion: There is a class of problems that are known to be undecidable. So even with infinite time and the best computers you cant find a solution. One of those problems is the well known halting problem. It loosely states: Can you decide if a given computer and an algorithm eventually stop running or run forever. This is completely trivial for most computer programs. 1. Does it have an loop, it cant escape => never halts. 2. Does it every repeat a state it was already in => never halts 3. Does it have no means of repeating code => always halts. But there is a proven program where you cant tell if it halts or not and therefore the problem is undecidable (for every case).
Lex looks somewhat out of it in this interview. Obviously he is a very accomplished person, but perhaps he should delegate more time as to be able be more present for interviews such as these.
From what I understood, the title means that if we were given, like, n questions about NP algorithms such as "Is this algorithm P" and had the correct answer to them, then the probability that the answer is correct would be ~3%, is what he believes? It's just that the title weirded me out, that's all.
no, he believes that the probability that the Conjecture P = NP is true is about 3%. (thats his confidence in the answer). So he thinks there is a 97% chance that there exist at least 1 NP problem that cannot be reduced to P which would make the conjecture P = NP false.
@@eragon78 But then it's become hard to understand the meaning of the statement itself. 3% of a statement where we can't take samples being true is very hard for me to get my head around. I am not very knowledgable in probability and statistics though, so maybe it does make sense in some way
@@iamtrash288 well, its pretty much just pulled out of his ass. Its not a real statistic. Its a confidence ratio. Like, if I say something like "Im 90% sure I left my keys in my house", thats like saying I am 90% confident that I left my keys in my house. And confidence ratios do have ways to measure them to a degree, but in any non incredibly technical way,they are usually just gross estimates based on a gut feeling. Basically, by saying "I think the chance P = NP is 3%" is just him saying he thinks its VERY unlikely but not quite impossible or even incredibly unreasonable, just very unlikely. Like, if he said he's 50% sure, then he doesnt really know either way. If he said he was 70% sure, then he thinks its more likely than not, but still a decent chance it isnt. 90% sure means hes really likely, but the chance that its not is still somewhat reasonable. 97% means that he thinks its VERY likely, but that there is a non-negligible chance it isnt. something like a 99.9% would mean he thinks its almost certain it is the case, but not quite 100% positive, there is still some minuscule doubt, and etc. Its just like an estimation. Not a rigorous thing. (at least in this case. Confidence ratios can be rigorous, but usually only in more like technical philosophical ways but thats not really what this is).
@@eragon78 hm... I see. it's just strange to see him speak that computer science is an offshoot of mathematics and that they have to be rigorous and use such a confusing expression I guess
@@iamtrash288 yea, its a bit weird, but its a pretty hard topic to talk about rigorously. We know a lot about the problem, but its still an unsolved problem for a reason. Its really complicated and difficult. So we can say some stuff about the problem, but there is a lot we just really cant say because we dont know yet. But yea, the title is definitely a bit misleading. Its not really clear at all.
Nope, P=NP. 100% I have the polynomial solution for the SAT NP complete problem. I don't know where or how to publicize my finding in magazines. Any help in this regard is highly appreciated.
@@mohancvp9723 If I were you I would start a Masters degree in Comp. Sci., and then go on to PhD and publish the paper in that context. Or discover an error in the original arguments.
If p does not equal np then there should be some way to map computational irreducibility if computational irreducibility can't be mapped and demonstrated then we may be left with the question why not. When Wolfram showed his branch and fold mapping of tick tack toe surely even with such a simple game you could demonstrate where harder or softer computation is necessary.
The real question is not, "is N=NP?" Of course it is. When N=1 then P=NP, how could it not be?!? Think about it: can you you determine the distance between one location(TSP) or if this 1 ball fits in this bag(Knapsack) in polynomial time? Sure. I could crush 4-sqaure Sudokus all day... The REAL question is, "at what point, if ever, does N *STOP* being equal to NP? I think there is a 2-3% chance that N != NP. The 97% who say otherwise are quitters grappling their own limitations IMHO. More evidence that when this problem is solved it won't be by a "professional" mathematician or a PHD from from some Information of Tech school in a lab, but rather an out of the box thinker with a laptop who's out of the box idea came from not going into the box in the first place. "Thats an easy one... If we were physicists we would just declare it to be true." - this only works if you say if with a lugubrious Tennessee accent and begin your sentence with, "I do declare..."
P = all the stuff we can do now with computers. NP = all the stuff we can't do yet (at least within a realistic amount of time) Example: What is the most efficient route to visit every Walmart once. This would take years to calculate. Also has other applications like motherboard layouts. The 3% thing is asking, what are the odds that we can use our current P methods to solve those really hard NP problems but we just haven't figured it out yet. Lex (and myself) was surprised the odds were that high.
the very important part of this is that some problems that thought to be NP at the beginning was later discovered as P.
That's why we ask is there a chance that all NP are actually P and we simply approach them wrong way.
explain ur thoughts more
We do approach the issue from all angles, some people are still working on particular problems. The reasons "does P equal NP?" is a very natural question is that some problems are NP-complete, and showing only one of them to be P is really the same thing as showing P=NP.
It OK if not all NP are P. It would still be amazing if someone proves even one NP-Complete to be P because then it means that all NP-Complete = P.
@@chunkyMunky329 by definition, a language L is NP-Complete if there exists a polynomial time mapping reduction from every language in NP to the language L. Mapping reductions are transitive, meaning that if one NP complete language was shown to be in P, then not only would NP-complete = P, but NP=P.
@@jomez2841 Wrong
“If we were physicists we would have just declared that to be a law of nature.” 😂
That bit was hilarious. Especially the part where you give yourselves more Nobel prizes if you find out you were wrong.
what a troll, poor physicists
First law of computer science? 👀
This is probably the best explanation of P vs NP I've heard.
I agree.
Hackerdashery's video was my first introduction to it, and it's great too!
I completely agree; he explained in under 5 minutes what takes people hours and hours to learn.
@@stoopidpants explanation for the layman. formal definitions are needed if you need to prove, via polynomial-time reductions, that a given problem belongs to a particular class.
@@pussiestroker Yes, obviously. But what I was saying is he explained a concept that's so fascinating it took me a REALLY long time to understand. This is just an extremely good example of what I call the "Feynman Effect" wherein a person has taken a complex topic and made it perfectly accessible, on a lay level, to just about anyone willing to listen for 5 minutes. Even after hearing it a few times I still can't explain it as well as he does; no even friggen close.
Not going to pretend I really understood any of that, but it sounds like you guys are having fun and that’s what makes this enjoyable.
Indeed
It's super interesting stuff you learn in CS curriculum. If tomorrow it was discovered P=NP, computers overnight would become super computers that would be able to do unimaginable things, solving world problems including a possible cure for cancer (the idea is to make an algorithm that could quickly compute customized treatments for individual patients with cancer, diabetes, AIDS, etc.)
The gut feeling though is that P != NP, but there is no formal proof of that yet.
@@jaftem2x P=NP doesn't mean automatically that computers become super computers. Most problem that we usually talk about which are in P can be solved "quickly", but we can easily find problems in P that solving them will take so long that one life time will not be enough. If we do manage to prove that P=NP, there is a good chance that the hard problems in NP are actually in the part of P which take very long time to solve. We do, however, have many tools to "almost" solve problems in a short amount of time, for example, using all sorts of heuristics and probabilistic methods. If our goal is to solve hard problems quickly, this is a much better method, than trying to prove that P=NP.
@@eofirdavid "but we can easily find problems in P that solving them will take so long that one life time will not be enough"
I assume this would be in the cases where, as Scott discussed, the exponent of the polynomial function is large?
@@synchronium24 Yes. The degree of the polynomial is quite important when we speak about running time. As Scott said, linear, quadratic, and in general small exponents are "fast". On the other hand, if we have a problem which is solved in n^10 time and even for a very small input size n=10, we will need 10^10 computer actions to solve it. If each of these actions in such an algorithm takes 1/1000 of a second, then it will take more than 100 days to finish it.
In most algorithms, the input size is much larger than n=10, to the point that in some of these problems even linear and quadratic is too much.
What I find so interesting about theoretical computer science, is that many of these problems are fairly easy to understand. Stuff like sorting numbers or coloring maps. Yet when you analyse their complexity, you find interesting relations such as that some problems can be reduced to other problems, meaning that there are sets of problems that are essentially equivalent. You can take the algorithm that solves one of those problems and use it to solve any of the other in the same set by transforming the input and the result.
I find it fascinating that problems can be "ranked" by their difficulty and what the landscape of algorithmically solvable problems looks like.
I wonder what implications t will hv on philosophy
"in p" vs "np" - very confusing choice of words
The way it's described here it sounds like P=NP means: Does any hard to compute algorithm who's solutions can be checked easily, actually have an alternative easy to compute algorithm, that we just haven't found yet? Is that right?
Pretty much yes. A different way of viewing the class of NP is like this: We have a problem where we can try one possible solution out of many in a small amount of time. But to always find the correct solution we need to check alot of possible solutions. If P = NP holds, then we will always check the correct solution first. So to speak we are always lucky.
Lets say we want to solve a sudoku where 78 spaces are already filled and we know the last 3 spaces contain 1,2 or 3. A possible Solution contains 3 numbers that might fit the board but probably dont comply with the rules. So we have to check (1,2,3),(2,1,3),(3,1,2),(1,3,2),(2,3,1),(3,2,1). If P = NP we can find a way of sorting our possible solutions in a way that we just try the correct one. And that is without actually solving the sudoku. If this leaves you suprised: "But wait that is all you have to do in Sudoku, find the correct set of numbers". Then you know why most Computer scientists say it cant be P = NP.
@@Schnorzel1337 Adjust the environment so the physics of the environment will dictate that the correct answer always rises to the top instead of interacting directly with the "solutions". In a sense, make laws for your program that dictate certain influences should take hold where correct answers are favored and incorrect answers are demerited. Do this to an extreme degree until you can reach certainty, shift the need for probabilistic thinking one floor up so you can deal with the program in a more sleek manner.This is different from machine learning where you recognize patterns because this is more of you directly establishing laws for your environment.
Where do laws arise from?
I didn’t understand a single word of this. But I’m glad guys like this exist.
It's not that hard to understand really, there was just way too little context if this is totally new to you. If it was like a 1 hour course with some drawings and more examples to guide it, I think most ppl would be able to understand what P and NP problems are, and what the question P=NP? means. During my CS courses this was not the first lesson of theoretical CS, it had a few hours of lead in lets say. What can be a lot harder/impossible, is proving that some given problem/solution is P or NP.
@@frydac You are underestimating how stupid I am.
@@spungoflex3285 it's okay buddy, that just means dummies like us have to work a little harder.
@@spungoflex3285 Very abstract, if you play a computer game for the first time you got so many options and ways to achieve victory that you are confused and take forever to complete it. But if the equation P = NP holds, then every game comes with a book that 100% details how the game can be beaten, you still have to play the game, but you know exactly how.
Curious is if P=NP are dreamers, glass half full, lottery players and PNP are realists, glass half empty, hex players?
When I was working I never had the time to think about whether P = NP has too busy thinking about the latest project end date or whether T equals chips.
There is a 100% chance I'm a PIMP
well said
That’s a pretty high chance
No Cadillac. No perms you can't see.
Well played
sounds so fantastical to even expect that such an amazing thing could be possible at all.
I really want to understand this conversation
It's not really that hard.
Imagine a simple algorithm, it has an input and an output. The algorithm has a set of operations to do on the input to get the output, and we can count them.
We then say that an algorithm is of complexity O(n) if, with an input of size n (you can think of an array of n elements for simplicity) we need to do n operations to get the output.
We call P the set of problems of complexity O(n^a), where a is a natural number. These are problems that we can solve easily with our current computer, even with huge inputs.
We call instead NP problems that are of complexity O(2^n) or similar, basically where n Is the exponent. This means that for every new element you have in input, the number of operations you need to do at least doubles. You can see where the problem is.
So why are they asking if P=NP? Because if we find a way to solve an NP-complete problem (meaning all other NP problems can be reduced to that) in polinomial time, then we can solve all NP problems in polinomial time and it would be a revolution for computer science and mathematics
@@AL3X2011 well yeah that's my background so i probably took some things for granted, but this channel talks pretty advanced topics so i hope people know at least the basics of cs
@@AL3X2011 you mentioned that most don't know what an array is...I also pondered over what "0(n)" could mean, tried to picture in my mind what "n elements" might look like, wondered where the "a" appeared from in the previous "0(n)" thing, and then we learned that NP describes "problems of complexity 0(2^n) or similar" apparently, which brought me back to ponder over what "0(n)" means...🤷♂️
@@Layneee like the traveling salesman model, but applied to a comedian doing circuits of clubs, maybe a picture like that
@@adamdaly4847 imagine a list of n numbers, okay that's your array. Imagine i write a program that sums all those numbers, well i would have to cycle through the array adding the number to the sum. This costs O(n), meaning i need to visit all numbers of the array once to get my result. If i needed to visit them all twice, the cost would be O(2*n).
It's pretty hard to explain it to someone with no cs background whatsoever though
If say for a 4 colour sudoku you make a grid for each of the 10 4 colour combinations with 2 1’s for every row subgrid and column representing a pair. Then if you sweep your possible 1’s there will always be at least 1 of the 1’s that is invalid.
It's like having a p time oracal where every time you sweep the 1’s at least 1 of the 1’s can be crossed off.
Scott Aaronson is a comedian omg his joke I'm dying laughing
So you're telling me there's a chance?
It's uncertain what the probability is
And if the probability itself is uncertain, you cannot say what chance is there
@@arnavrawat9864 It was a joke. It's from a meme.
However, I never implied that the chance is known.
So your whole comment is redundant.
@@stefanaursulesei6104 cool
Mask
This is quite well explained.
Oh, I know.
My favorite big-O, which is very NP, is 2^(2^n). The doubling doubles!
Back in the day, one line of O(2^(2^n)) code would make your server kneel. Good times.
That would be 2exp or exspace not np
I have to go to bathroom really bad now for some reason
This is one of the 7 Millenium Prize Problems outstanding as of 2000. Solving or in (all) most cases, proving, the idea true or false will net you USD$1 million. Only one of the 7 has been solved, the Poincaré Conjecture, which dealt with hyperspheres. It was solved in 2006 by Russian mathematician Grigori Perelman, who refused the $1 million cash prize. Fascinating.
Graph coloring problem is solved recently last in 2-3 years turns out any graph can be colored with Minimum 4 colors.
Solution was very inelegant it was brute force approach but meh we got the answer
1% enjoyed this to the fullest. Thanks for the mingasm.
Lol five dislikes from Nobel prize in physics recipients
Wait he says 2-3% odds that P = NP right after saying if he were a physicist he would declare it so that N not = P. The 5-sigma standard is highly offended.
Well if you look at concrete trials that have been made to transform NP problems into P solutions, so far all of them failed so we easily get to 5-sigma standard.
Maybe a bit harsh to physicists though.
@@SymEof fair point. Probably some fairly deep philosophy of science happening comparing natural experiments with formal computational "experiments." It's still bogus imo to connect 2-3% odds to absolute certainty for a physicist.
@@SymEof there are NP problems that can be solved by reducing the problem to another solution that exist in P. The issue is that we need to prove that every NP problem can be solved that way, it's a math demonstration, and they are very complex and long to do on such argument. there is a prize for one that can prove it, of several milions $.
@@SymEof well, 5-sigma is more of an experimental probability of significance though. It doesnt really apply to mathematical proofs.
Also, you cant have a proper probability rating for whether a conjecture is true or not. You can have a confidence rating (which is what that 3% estimate would be) but its not quite the same thing as a probability in the experimental sense.
Also, there are many NP problems that have been reduced to P, but there are also many NP problems that have NOT be reduced to P. The NP problems that have been reduced to P are obviously the ones where it was possible. But any NP problem that cannot be reduced to P could very well be impossible to reduce which is why it hasnt been done yet.
Actually, more on that, there is a specific type of NP problem that has shown up many times in many different fields and problems that has not yet been reduced to P, and its conjectured by many that it is impossible to reduce it to P. This may actually be the key to solving the P = NP conjecture but nobody has devised a proof yet so that remains to be seen.
@@iM7SnaKe Yea, its one of the Millennial problems. That alone has a $1 million prize for solving it. And thats just 1 of the prizes for it.
I predict P=NP for a large enough N
It is P=NP. 100%. I have the polynomial solution for the SAT NP complete problem. I don't know where or how to publicize my finding in magazines. Any help in this regard is highly appreciated.
P = NP
P/P = NP/P
1 = N
1 = true
Since N stands for "Not" the "not" part of this problem is true (N=1).
So since the ' "Not" polynomial' part is true, P != NP
I don't think that's how that works lol.
Quick Mafs
🤣 The = here does not mean the arithmetic equality but the mutual inclusion in the set theory P ⊆ NP and P ⊇ NP
Give this man a million dollars!
I appreciate you guys for not taking this seriously 😊
Factoring numbers is not known to be in P or NP.
It is in NP. Without any theory, if it would be a problem in P we could solve it easily rendering most encryption techniques useless.
It is known to be in NP. It is true that it is not known whether it is or is not in P.
I should have been more clear -- it's not known if factoring is in NP-complete or not.
Good clip.
What’s the difference between physicists and mathematicians you ask? “If we were physicists we would just declare that P =/= NP as a law of nature and give ourselves Nobel prizes for it's discovery, and if later it turned out that we were wrong we would just give ourselves more Nobel prizes.” 😂😂😂
Mathematic Axioms beg to differ when it comes to declaring things to be true smh.
Can you please do a long-form interview with GPT-3? Its responses depend heavily on the questions asked and I think you could extract some fascinating answers from it.
Interesting, freelance predictive AI in the late 90s using methods like Bayesian probability, hidden Markov models, deterministic selection, etc... Did a major multi year project to predict stock dumps. Worst years of my life. It is extremely interesting to hear about the direction classes and education has take in cs. I still have a intrest in AI but wouldnt trade the life I have now. Work with my hands, designing and building things others use, and the connection this process gives me with my family is so rewarding. -David Dennis
This guy is really gonna eat his words when I drop my P = NP proof next year.
Well, its one of the Millennial problems so if you do, you get $1,000,000.
We're still waiting...
Times up dude!
@@pawanbhatt314 you didn't see it? He showed me his proof and I checked it. It's legit, just a little too long to fit in a RUclips comment but P=NP does in fact hold :)
Dungeon decor is good for the cast
I hove no idea how I came to this video an I have no idea what's going one
Good brain exercise. I'll have to google the three divisor problem.
P=NP is an axiom.
I have to P
So there is a 3% chance that a problem is equal to no problem?
Where r u guys.
so theres a chance hmmm
so if its easier to check 1 solution, can you check an exponential amount of solutions in polynomial time.
No, that would by definition take an exponential amount of time on a deterministic turing machine. On a non-deterministic turing machine, yes. Infact, that is how you go about proving that a problem is in NP: you prove a solution can be checked in a polynomial time (known as the certificate) then a non deterministic turing machine can simply non deterministically check every possible solution (in polynomial time)
At this question at the end of the show to every guest in the hot seat please this was pretty interesting thanks
god damn this sounds like my numerical methods class
P=NP. is such an elementary question if you look at 1:58 you can see how annoyed Lex is that he took 2 minutes to explain something so simple. Basically to verify a question you have to solve the question, because you tend to just redefine in maths. But is this ALWAYS true? Is verifying always just doing the solving again. I always get annoyed by these questions, because instead of solving the million dollar question people just find ways of explaining it. I truly think some people like to make things "complex"
this guy passed discrete math first try
GANs are the best hope I have for P=NP
If you are talking about Neural networks I can assure you, no neural network can ever prove that P =NP. Think about this way. There is no known algorithm specificly designed for a problem that breaks open the NP part. And now you throw that all in the wind and use a generic method to solve that? Very very unlikely.
@@Schnorzel1337 www.nature.com/articles/d41586-020-03348-4
Honestly wondering what you think of this result. I don't have a ton of context but I have understood protein folding to be one of the most classic examples of an NP problem, is that not the case?
@@Deez-Master Very interesting for that field of reasearch. But unless you can prove that you can understand the folding of every possible protein you are not one step closer to P = NP. In my experience it is often easy to find a NP problem for which some inputs are trivial to solve. Lets say you want to calculate a solution for the Traveling Salesman Problem, which asks for a minimal tour through n different cities and returning back to the starting city. This problem is NP-hard. But if all cities lie on a grid or a structure of some sort, it becomes trivial for any number of cities.
The general case is what breaks the argument.
Excursion: There is a class of problems that are known to be undecidable. So even with infinite time and the best computers you cant find a solution. One of those problems is the well known halting problem. It loosely states: Can you decide if a given computer and an algorithm eventually stop running or run forever.
This is completely trivial for most computer programs. 1. Does it have an loop, it cant escape => never halts. 2. Does it every repeat a state it was already in => never halts 3. Does it have no means of repeating code => always halts.
But there is a proven program where you cant tell if it halts or not and therefore the problem is undecidable (for every case).
I thought it was a discussion on statistical probability.
1:35 ok!!
I think it's about 1 in 14,000,605.
How did you arrive at this number? Genuinely interested
@@vitorodino8760 Dr. Strange searched for it (nondeterminstically) in Avengers: Infinity War: ruclips.net/video/ZCPN9SfdH7c/видео.html
@@vitorodino8760
"Infinity Wars".
What if the P=NP algorithm is to _know_ the answer?, like Neo.
If you know the answer, then it's not a problem and therefore not in P or NP.
Lex looks somewhat out of it in this interview. Obviously he is a very accomplished person, but perhaps he should delegate more time as to be able be more present for interviews such as these.
From what I understood, the title means that if we were given, like, n questions about NP algorithms such as "Is this algorithm P" and had the correct answer to them, then the probability that the answer is correct would be ~3%, is what he believes?
It's just that the title weirded me out, that's all.
no, he believes that the probability that the Conjecture P = NP is true is about 3%. (thats his confidence in the answer).
So he thinks there is a 97% chance that there exist at least 1 NP problem that cannot be reduced to P which would make the conjecture P = NP false.
@@eragon78 But then it's become hard to understand the meaning of the statement itself. 3% of a statement where we can't take samples being true is very hard for me to get my head around. I am not very knowledgable in probability and statistics though, so maybe it does make sense in some way
@@iamtrash288 well, its pretty much just pulled out of his ass. Its not a real statistic.
Its a confidence ratio. Like, if I say something like "Im 90% sure I left my keys in my house", thats like saying I am 90% confident that I left my keys in my house.
And confidence ratios do have ways to measure them to a degree, but in any non incredibly technical way,they are usually just gross estimates based on a gut feeling.
Basically, by saying "I think the chance P = NP is 3%" is just him saying he thinks its VERY unlikely but not quite impossible or even incredibly unreasonable, just very unlikely.
Like, if he said he's 50% sure, then he doesnt really know either way. If he said he was 70% sure, then he thinks its more likely than not, but still a decent chance it isnt. 90% sure means hes really likely, but the chance that its not is still somewhat reasonable. 97% means that he thinks its VERY likely, but that there is a non-negligible chance it isnt. something like a 99.9% would mean he thinks its almost certain it is the case, but not quite 100% positive, there is still some minuscule doubt, and etc.
Its just like an estimation. Not a rigorous thing. (at least in this case. Confidence ratios can be rigorous, but usually only in more like technical philosophical ways but thats not really what this is).
@@eragon78 hm... I see. it's just strange to see him speak that computer science is an offshoot of mathematics and that they have to be rigorous and use such a confusing expression I guess
@@iamtrash288 yea, its a bit weird, but its a pretty hard topic to talk about rigorously. We know a lot about the problem, but its still an unsolved problem for a reason. Its really complicated and difficult. So we can say some stuff about the problem, but there is a lot we just really cant say because we dont know yet.
But yea, the title is definitely a bit misleading. Its not really clear at all.
Intuitively, P!=NP.
Yep but human intuition is not always correct
Nope, P=NP. 100% I have the polynomial solution for the SAT NP complete problem. I don't know where or how to publicize my finding in magazines. Any help in this regard is highly appreciated.
@@mohancvp9723 If I were you I would start a Masters degree in Comp. Sci., and then go on to PhD and publish the paper in that context. Or discover an error in the original arguments.
If p does not equal np then there should be some way to map computational irreducibility if computational irreducibility can't be mapped and demonstrated then we may be left with the question why not. When Wolfram showed his branch and fold mapping of tick tack toe surely even with such a simple game you could demonstrate where harder or softer computation is necessary.
(P=Np) = 🌞
The real question is not, "is N=NP?" Of course it is. When N=1 then P=NP, how could it not be?!? Think about it: can you you determine the distance between one location(TSP) or if this 1 ball fits in this bag(Knapsack) in polynomial time? Sure. I could crush 4-sqaure Sudokus all day...
The REAL question is, "at what point, if ever, does N *STOP* being equal to NP?
I think there is a 2-3% chance that N != NP. The 97% who say otherwise are quitters grappling their own limitations IMHO. More evidence that when this problem is solved it won't be by a "professional" mathematician or a PHD from from some Information of Tech school in a lab, but rather an out of the box thinker with a laptop who's out of the box idea came from not going into the box in the first place.
"Thats an easy one... If we were physicists we would just declare it to be true." - this only works if you say if with a lugubrious Tennessee accent and begin your sentence with, "I do declare..."
P = all the stuff we can do now with computers.
NP = all the stuff we can't do yet (at least within a realistic amount of time) Example: What is the most efficient route to visit every Walmart once. This would take years to calculate. Also has other applications like motherboard layouts.
The 3% thing is asking, what are the odds that we can use our current P methods to solve those really hard NP problems but we just haven't figured it out yet. Lex (and myself) was surprised the odds were that high.
What are the odds that there exists a solution to solve those really hard NP problems that belongs in P*
Could have been my lecturer
Let P = NP
N = P/P
N = 1
QED
Seems a bit high but okay
How DARE you post such a title
But also that was WAY higher than I would have expected to hear
This is hilarious 😂
1:12 K!!
what
Nobel prizes for everybody! (3/everybody)
Clickbaity title
Mmmkay
Dear yt stop recommending me this jew appreciation channel thanks
I’d say it is more like 0.0000001%
P=NP