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. For a language in NP, it is almost 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 virtually no way to guarantee (or prove) that a more efficient algorithm does not exist. From this perspective, in all attempts to prove P $\neq$ NP, all we can do may be to try to provide the best clues or "evidence" for P $\neq$ NP. Accordingly, this paper is not intended to provide a rigorous proof of P $\neq$ NP, but rather provides stronger "evidence" for P $\neq$ NP. We introduce a new language, the Add/XNOR problem, which has simple structure and perfect randomness, by extending the subset sum problem. We propose Conjecture 1 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 $\neq$ NP. Furthermore, we define two operators whose corresponding truth tables form two Latin squares. Based on these two operators, by giving up commutative and associative properties, we obtain a new algebra, the magma algebra equipped with a permutation, and successfully achieve Conjecture 2 and 3, the first computational problems considered resistant to the meet-in-the-middle (MITM) strategy. With an $n$-bit input, the problem in Conjecture 2 is believed to require an exhaustive search over half of the search space to solve with complexity $O(2^{n-1})$, and the problem in Conjecture 3 is supposed to require an exhaustive search over the entire search space to solve with complexity $O(2^n)$, by far the strongest evidence for P $\neq$ NP. In contrast, both SHA-256 and AES can be reduced in computational complexity by meet-in-the-middle attacks. Briefly, Conjecture 1 indicates that meet-in-the-middle is the optimal solution for the Add/XNOR problem; Conjecture 2 and 3 suggest that the Inverse Problems can withstand meet-in-the-middle attacks.