What are the most famous unsolved mathematical equations?

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

Implications

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.

What are the most famous unsolved mathematical equations?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s