“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!”

The concept first

When we study algorithms, we must have encountered the traveling salesman problem in dynamic programming (TSP)!

TSP is a NP complete problem, and today we are going to talk about the first of the seven Millennium Award problems.

  • Note: $1 million for each millennium Grand Prize puzzle solved

In fact, Bengua in a recent article “The Problem Maker: The Inevitable” Algorithm Design and Analysis “! Mentioned in a mouth:

“Know the P/NP problem! I have the illusion that I have touched the human mathematical ceiling. 😵”

Now look at this sentence, I am small, the pattern is small! This sentence should read:

“P/NP problems should be the cognitive ceiling of modern humans! It has the power to overthrow the whole world! 💪”

What exactly is a P/NP problem??

In a word:

If the solution of a problem can be verified in polynomial time (P), can it be proved that the solution can be found in polynomial time (NP)?

  • Polynomial time: such as O(N2), O(N100), O(N200), etc.

If you can prove yes (P = NP) or no (P ≠ NP), you get $1 million.

In the most common sense, if we prove P = NP, it means: (When we propose a method to verify a problem, we can obtain the solution of the problem!)

This is a very scary sentence! Modern computer science and information technology is based on P ≠ NP. If P = NP is proved, the world will usher in great changes!

  • A 2002 survey of experts in the field of P/NP found that the ratio of those who believed P = NP and P ≠ NP was 9:61.

Take a chestnut

For example 🌰 :

Sudoku problem, it’s easy to verify, just walk through the rows and columns to check, order n2 time.

But, conversely, if given a Sudoku problem, can you solve it in polynomial time?

So far the verdict is: not sure!

Take another example 🌰 :

When I tell 319 that it is the product of two primes, what is 319 the product of two primes? What if it’s a very, very large prime number?

This problem, like sudoku, can be verified in polynomial time (just do the multiplication), but it is not certain that it can be solved in polynomial time.

That’s what they are: easy to verify, but hard to solve!!

There are many more examples 🌰 :

We can verify it in polynomial time (P: Polynomial time), but we are not sure if we can find this solution in polynomial time (NP: nondeterministic polynomial time).

For example: resource scheduling problem, graph coloring problem, Hamiltonian loop problem, travel salesman problem……

  • Wiki: List of NP-complete Problems

These seem to be math problems, information technology problems, but they are reflected in all aspects of life!

The currency pawn

If P = NP, modern cryptography would completely collapse (i.e., bitcoin and other cryptocurrencies would simply disappear).

We know asymmetric cryptography: public keys can be computed from private keys, but private keys cannot be computed from public keys.

This asymmetry is the most important guarantee of safety!

Private key (K) * G = Public Key (P) Public key (P)/G = Private key (K)Copy the code

Perform G on the private key (K) to get the public key (P). This is easy! (Easy to verify)

But by the public key (P) to do G operation of the inverse operation to obtain the private key (K), is currently considered: very, very, very difficult, almost impossible, this is the most important basis of encryption security! (Solving difficulty).

If P = NP is proved, then we can solve the private key by computer in polynomial time. There is no encryption!! So, the encryption system is broken!!

You might be wondering: what if this multiple time is big, like O(n100)?

A: As long as P = NP, even if the polynomial time is large, we can figure it out sooner or later! Because the problem doesn’t change, the power is constantly improving. Quantum computing

That said, if modern cryptography breaks down, the benefits far outweigh the $1 million cost of cracking the P/NP problem

Man and machine

Even more alarmingly, if P = NP is proved, the line between man and machine begins to blur.

Scott Aaronson, a professor at MIT’s Computer Science and Artificial Intelligence Laboratory, said:

“If P = NP, the world would be a completely different place. Ideas are no longer valuable! When a problem is identified, the distance from recognizing it to solving it is no longer too distant. Those who like symphonies can become Mozart. A person who likes to argue step by step can be a Gauss. Art and intelligence are modelled by the deep architecture of computing.”

It means that no matter how complex a problem is, if we can verify it in polynomial time, it means we can solve it in polynomial time. Even art creation!

A computer can imitate a particular person accurately. Online identification will become so difficult that physical means will have to be used;

Everything belongs to a

Chopin once said:

“Simplicity is the ultimate achievement.”

Let’s paraphrase the P/NP problem a little more:

P/NP ultimate question: Can all the complex problems in the world become simple problems?

No one knows.

Perhaps humans will ultimately fail to find this simplest truth, just as characters in games fail to understand us.

Is the universe chaotic? Or is it orderly?

Wow, this is the ceiling. QAQ? All return to solitude……

Recommended reading

  • Discussion on P vs. NP
  • What are elliptic curve encryption and hash functions? What is asymmetric encryption? The mathematics of bitcoin
  • One of the world’s seven mathematical problems: P and NP
  • A review of solving NP hard problems
  • P does not equal NP… ?
  • What would the world be like if P=NP?
  • The latest proof is challenged: why is the P/NP problem so hard?
  • Scientists have discovered that human consciousness is linked to the chaotic nature of the universe

I’m Nuggets Anthony, output exposure input, technical insight into life, see you next time ~