If you were expecting an explanation I just pranked you, because I don't know what it means either.


So please someone explain to us in baby terms what P=NP means and how it relates to the plot of the story.

I dont know how did you even get this kind of question?

In simple terms, P=NP means, all problems that are easy to verify (meaning answer are there given possible situations), are very difficult to solved in polynomial time. That is a very simple definition, it can't get any simpler. 

P = a group of question in which various algorithm can provide answer in polynomial time

NP = a group of question for which answer can be verified in polynomial time

Polynomial Time = a time require to run your algorithm to solve the problem (a very basic definition)

Algorithm = A strict set of finite sequence or instructions to solve a problem

So it is widely believed that P ≠ NP (but not proven as of yet) meaning there are problem whose answer can easily be verified but in order to solve that answer, a solution (to compute) is not there. 

So the major question this problem proposed "every problem whose solution can be verified, can also be  solved?" 

And that is why it should not be written P=NP (because it is not proved yet) but P versus NP, so both cases are not proven P=NP or P ≠ NP. If one is proved, the other will be eliminated itself.

Basic example: 

If someone wants to built 2 towers (not actual just putting blocks) by stacking rocks of different masses but also want that those towers must have same mass / weight, one would have to put the rock of same masses together, right? But how do one thinks of a way to check which rock should have same mass or how the devision of rocks will work while building tower? 

Perhaps you would divide the rocks randomly and then measure it on a scale to divide the mass, it is called a check process, you can easily verify or check the solution but can not solve it outright. 

If one has 100 rocks to start with, then 2^{100-1}-1 = 630000000000000000000000000000 (Six hundred thirty octillion) ways to divide the rock to balance the mass. Which is impossible to solve for any human or computer at this time. 

Funny but true: If one want to check a unique way to find a solution every day, it would take 1.3 x 10^22 (thirteen sextillion) years to compute the solution, and one would need two trillion (2,000,000,000,000) different ways of dividing the rocks every second to check all the different ways.

So even a most powerful computer or system exist today it would take 1,000,000 combination per second and requires 2,000,000 computers working since the origin of universe to test all the combinations to find the exact solution, on how a mass of those towers should be divided, if one has just 100 rocks. 

this is such a long one

@Nauriya Thanks for this!! 

Therefore, through computing, as of now, its impossible to run those calculations. So to prove that P=NP its not a matter of coming up with strong enough computers but a matter of creating an algorithm that can run those combinations in a short time? 

 bibi:

@Nauriya Thanks for this!! 

Therefore, through computing, as of now, its impossible to run those calculations. So to prove that P=NP its not a matter of coming up with strong enough computers but a matter of creating an algorithm that can run those combinations in a short time? 

Only a strong computer can run an algorithm of such complexity. Yes no such algorithm exist for NP-complete system and no computer either, that can actually satisfy P=NP. And any logarithm that will solve the problem in polynomial time, will only consider as a true algorithm to satisfy all the problem exist in NP-complete system. 

It can open million application where humanity can benefit from. 

In series it was mentioned that Alzheimers could have been solved if Xi would have allowed PZ to stay as he solved the problem. Hinting it could help find those nasty proteins that allows cancerous cell to grow, or other cells that paves the way to other diseases.  We can easily target ill cells of any disease or study the origin of neurogenic disease such Alzheimer and Cancer, to find a way to solution without harming a body. 

Although it is disputed that it would have such great effects, but it is not denied either, as proof of P=NP would eventually open new doors to solution in various field of science, and incurable disease might be one of those problems that can finally be solved. 

 Nauriya:
In simple terms, P=NP means, all problems that are easy to verify (meaning answer are there given possible situations), are very difficult to solved in polynomial time.

You have it backwards (although you explained it correctly later in your post).  If P=NP, it means that all problems that can be verified in polynomial time can be solved in polynomial time.

 Nauriya:
Polynomial Time = a time require to run your algorithm to solve the problem (a very basic definition)

To be more specific, an algorithm is polynomial time if it runs in O(n^k) for some constant k, which means that the number of steps as at most some constant multiple of n^k for all sufficiently large n (n is the input size).

 Nauriya:
If one has 100 rocks to start with, then 2^{100-1}-1 = 630000000000000000000000000000 (Six hundred thirty octillion) ways to divide the rock to balance the mass. Which is impossible to solve for any human or computer at this time.

Actually there's a faster way to solve this problem, but it's still slower than a polynomial time algorithm.

1. Split the 100 rocks into 2 sets of 50 rocks.

2. For each of the two sets, generate a list of all possible sums.

3. Check if there's a number in the 1st list and a number in the 2nd list that add up to half the total mass.

There's also a probabilistic algorithm for this problem that runs even faster.

 bibi:
So to prove that P=NP its not a matter of coming up with strong enough computers but a matter of creating an algorithm that can run those combinations in a short time? 

If you find a polynomial time algorithm for any NP complete problem, it would prove that P=NP.  In the context of the P versus NP problem, usually we assume that the algorithm will be run on a Turing machine, so it's based on how many steps are required to solve the problem on a Turing machine.

If one NP complete problem can be solved in polynomial time, then every NP problem can be solved in polynomial time.  This is because any instance of any NP problem can be reduced to an instance of an NP complete problem, so you can solve the NP complete problem quickly, and then use the solution to get the solution to the other NP problem.

The problem that Nauriya described is a variant of the subset sum problem, which is an example of an NP complete problem.

i wanted to use less mathematical terms thats why.

Isn't it P(roblem)=N(ot) P(roblem) anymore once you solve it? 

Just kidding. ? 

 sunny11k:

Isn't it P(roblem)=N(ot) P(roblem) anymore once you solve it? 

Just kidding. ? 

I know you were kidding, but in case anyone is curious what they stand for...

P stands for polynomial.

NP stands for nondeterministic polynomial.  An NP problem can be solved in polynomial time by a nondeterministic turing machine.  This is equivalent to the other definition of NP (verifiable in polynomial time), because a nondeterministic turing machine can simulate a verifier, and a verifier can simulate a nondeterministic turing machine (sorry if this is confusing, but it would take a long time to explain it in detail).

I come here during my leisure time to be entertained and socially active. And you have opened a coaching class here, whether is an algorithm, mathematics, or programming.  have fun guys bye bye

 BLOOM:

I come here during my leisure time to be entertained and socially active. And you have opened a coaching class here, whether is an algorithm, mathematics, or programming.  have fun guys bye bye

People have kindly given their time to explain a complicated concept to people who are watching Basic Law of Genius. Their efforts are appreciated. Please be mindful of your words and how they come across. No one here is off topic or being "unentertaining", except you, If math offends you keep it to yourself.