What are the most famous unsolved mathematical equations? by @MaverickLin
Answer by Maverick Lin:
P = NP
This is one of the seven Millennium Prize Problems in mathematics. The discoverer of the solution of any one of the seven problems will be awarded a $1 million prize. This problem is notorious in Computer Science.
The Short Description
P is a set of relatively easy problems.
NP is a set of relatively very hard problems.
P = NP implies that all hard problems actually have very easy solutions.
The Long Description
This will take a while to fully explain, so try to bear with me if you want.
Much of CS is obsessed by how long does it take to execute an algorithm. Below is a chart of algorithmic complexity- it is usually described as a function of n, or the number of elements the algorithm has to manipulate.
The P stands for polynomial time. Polynomial time means that the complexity of the algorithm is O([math]n^k[/math])- basically cubic or above in the chart. So P is the set of problems that are solved in polynomial time. Algorithms that run in polynomial time are usually considered “good”.
NP stands for nondeterministic polynomial time. NP is the set of problems whose solutions can be verified in polynomial time. But the time spent solving the problem initially is undetermined- as far as we know, solving those take exponential time. In the picture above, the line that divides cubic and exponential is the “bad” line. Exponential time or factorial complexity is generally not good.
So does “P = NP” can be converted into, “If the solution to a problem can be verified in polynomial time, can the solution be initially found in polynomial time?”
The implications of P=NP are enormous.
If P=NP, then every hard NP problem would contain a hidden shortcut, which would allow computers to quickly find solutions to them.
If P != NP, then no shortcut exists and computers’ problem-solving capabilities will be always limited.
One practical example is cryptography. Computers’ inability to efficiently factor huge composite numbers form the cornerstone of modern cryptography- RSA public-key cryptosystem being the prime example (prime, get it?).
If you discovered that P=NP, you could essentially crack all the cryptosystems in the world. You would get access to all the bank accounts, government secrets (NSA), nuclear launch codes, anything.
As our Discrete Structures professor said, if you solve P=NP, don't go claim the $1 million prize. Bring it to him and you guys can rule the world together.
Edit: As per request, I am here to provide an example of P and NP. A simple example would be multiplication.
It’s a P problem to solve n * k- or 33 * 81 = 2,673. Bam. Done.
But it’s a NP problem to find the specific factors of 2,673- namely n and k. Why?
Because you can easily verify that 33*81 is 2,673, but solving for n and k given the product (2,673) is NP- n and k could be a wide range of numbers- 1 and 2,673, 3 and 891, etc…
Once the numbers get really really big, it will take exponential time to find the right factors.
Edit 2: As some have mentioned, I have missed some important details in an attempt to simplify the P=NP concept. The explanation above is barebones and minimum- think of it as a very basic primer or introduction to P=NP. In order to truly understand it, please consult more detailed sources. Cheers.