Paper 2024/2035

A Note on P $\neq$ NP

Abstract

The question of whether the complexity class P equals NP is a major unsolved problem in theoretical computer science. The key to proving that P $\neq$ NP is to show that there is no efficient (polynomial time) algorithm for a language in NP, which is almost impossible, i.e., proving that P $\neq$ NP is almost impossible. In all attempts to prove P $\neq$ NP, all we can do is try to provide the best clues or evidence for P $\neq$ NP. In this paper, we introduce a new language, the Add/XNOR problem, which has the simplest structure and perfect randomness, by extending the subset sum problem. We conjecture that the square-root complexity is required to solve the Add/XNOR problem, which is by far the strongest evidence for P $\neq$ NP. That is, problems that are verifiable in polynomial time are not necessarily solvable in polynomial time. Furthermore, by giving up commutative and associative properties, we design a magma equipped with a permutation and successfully achieve Conjecture 2. Based on this conjecture, we obtain the Add/XOR/XNOR problem and one-way functions that are believed to require exhaustive search to solve or invert.