P vs NP Problem

The P vs NP problem is one of the most interesting and unanswered questions in computer science. The solution learns that every problem that can be checked quickly (in polynomial time, called NP) can also be solved quickly (in multi-cycle time, called P).

The point is P and NP

1. Class P (Time of Polygamy):

   • This problem can be solved efficiently - in polynomial dimension with input size.
   • Example: Sorting a list of numbers using an algorithm like QuickSort or MergeSort.

2. Class NP (Nondeterministic Polynomial Time):

   • Although the solution to this problem may be complex, once given, there is a solution that can be quickly tested.
   • Example: Traveling Salesman Problem (TSP) - take a tour, check if the cottage is fast, but finding a short cottage tour is difficult.

Central question

P vs NP begs the question: If we can quickly find solutions to problems, can we also quickly find solutions to them? Is P formally equivalent to NP?

Why does it matter?

Deciding P vs NP has profound implications:

1. Cryptography:

   • The security of cryptographic systems like RSA depends on the difficulty of problems like prime factorization. If P equals NP, this problem can be solved quickly, compromising the security of world data.

2. Optimization with AI:

   • Many complex optimization problems of logistics, scheduling and artificial intelligence are NP-complete. If P is equal to NP, it will transform this industry and allow this problem to be solved efficiently.

3. Scientific Research:

   • Fields such as biology (protein folding), chemistry (molecular interactions) and physics (simulation of quantum systems) are often classified as NPs. Overcoming this will effectively accelerate scientific discovery.

Current Perspectives

Despite several decades of research, P vs NP remains unresolved. Many computer scientists think that P is not the same as NP, some problems are hard to solve, but easy to check. The issue is one of seven issues in the Millennium Prize, with a $1 million prize for clear evidence.

The Broader Impact

Understanding that P is equal to NP is beyond theoretical curiosity. It challenges our fundamental understanding of problem solving and the limits of computing. If P equals NP, it will represent a new limit of algorithmic capabilities, capable of solving problems that are currently intractable.

The results

The P vs NP problem is at the heart of theoretical computer science with important practical implications. The solution will not only advance our theoretical understanding, but will affect many real-world applications, from cybersecurity to scientific research. Until then, it remains a fascinating mystery that continues to inspire and challenge the brightest minds in the field.

Comments

[Gaoming]

Here we introduce a completely innovative block cipher algorithm, which we will name Eagle Encryption Algorithm. Through it, we can prove that P≠NP.

For traditional block cipher, for any known plaintext-ciphertext pair, the key is uniquely determined, and the security depends on the computational complexity of cracking the key and the assumption of the existence of a one-way function.

For the Eagle encryption algorithm, the key cannot be uniquely determined for any known plaintext-ciphertext pair, and even all keys in the entire key space can match a given plaintext-ciphertext pair. This may seem contrary to some common sense, but in fact Eagle has achieved it. We will briefly introduce its implementation principle later.

Because the key cannot be determined for each block, traditional attack methods are ineffective such as linear attacks, differential attacks, side channel attacks, etc. Furthermore, because all keys can match a given plaintext-ciphertext pair, any key cracking for a single block or multiple groups is impossible. The only way to attack is through brute force cracking. For short key block encryption algorithms, this satisfies the condition of a one-way function. According to the statement 'the existence of one-way functions=>P ≠ NP', it is equivalent to proving the open problem of P ≠ NP.

Returning to the core feature of the Eagle algorithm, for blocked plaintexts (keys) that meet the length of 2 ^ u, there is a completely independent and randomly generated hidden variable. The other hidden variable generated after completing Eagle encoding is only related to the blocked plaintexts, that is, the hidden variables before encoding and after encoding are independent of each other, have no relationship, and can be randomly generated separately. That is to say, ciphertext is only related to the hidden variables before encoding, while plaintext is only related to the hidden variables after encoding. Only plaintext and ciphertext are retained before and after encoding, and all hidden variables are directly deleted on the encrypted party after encoding is completed. This feature has been rigorously mathematically proven in the paper, and after being tested through programming code, it fully meets the expected results.

Paper：arxiv.org/abs/2203.05022
Open Source：github.com/NP-gaoming/Eagle-Encrypt
Email: [e-mail]

Welcome everyone to actively participate in discussions and promotions.