Paper 2024/2035

A Note on P $\ne$ 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 $\ne$ NP is to show that there is no efficient (polynomial time) algorithm for a language in NP. For a language in NP, it is impossible to prove that it is not in P, because we can only claim that no better algorithm has been found so far, and there is no way to guarantee (or prove) that a more efficient algorithm does not exist. It is impossible to prove P $\ne$ NP rigorously, as any problem with size $n$ and solution space $2^n$ has certain structures and properties, and there is no way to prove that more efficient algorithms that take advantage of these structures or properties do not exist. In all attempts to prove P $\ne$ NP, all we can do is try to provide the best clues or "evidence" for P $$ 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 time complexity is required to solve the Add/XNOR problem, making it surpass the subset sum problem as the latter has algorithms that break the square-root complexity bound, a better evidence for P $$ NP. Furthermore, by giving up commutative and associative properties, we design a magma equipped with a permutation and successfully achieve Conjecture 2, which is the first problem with exponential complexity that is believed to require an exhaustive search to solve, by far the strongest evidence for P $$ NP.