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.

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

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.

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.

I wonder what implications t will hv on philosophy

well said

That’s a pretty high chance

No Cadillac. No perms you can't see.

Well played

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.

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

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

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

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

Well, its one of the Millennial problems so if you do, you get $1,000,000.

We're still waiting...

Times up dude!

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.

Mathematic Axioms beg to differ when it comes to declaring things to be true smh.

It basically means solving impossibly hard problems, easily. Like, solving an equation spits out the nuclear launch codes or money transfer confirmation IMF codes. What's funny is, that's not even hyperbolic.

Proving something is also in NP. Given a proof you can easily verify it but there's no easy way to to find it.

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 😊

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

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)

If you know the answer, then it's not a problem and therefore not in P or NP.

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.

How did you arrive at this number? Genuinely interested

@@vitorodino8760 Dr. Strange searched for it (nondeterminstically) in Avengers: Infinity War: kzfaq.info/get/bejne/kKmAgZyEy8qsZ5c.html

@@vitorodino8760 "Infinity Wars".

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.

Yep but human intuition is not always correct

But also that was WAY higher than I would have expected to hear

What are the odds that there exists a solution to solve those really hard NP problems that belongs in P*