A Heuristic Proof of P $\neq$ NP

Ping Wang

Paper 2024/2035

A Heuristic Proof of P $\neq$ NP

Ping Wang

, Shenzhen University

Abstract

The question of whether the complexity class P equals NP is a major unsolved problem in theoretical computer science. 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 prove that P $\neq$ NP as it shows that the square-root complexity is necessary to solve the Add/XNOR problem. That is, problems that are verifiable in polynomial time are not necessarily solvable in polynomial time.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: P NP subset sum problem Add and XNOR problem complexity theory polynomial time exponential time
Contact author(s): wangping @ szu edu cn
History: 2024-12-22: last of 4 revisions; 2024-12-17: received; See all versions
Short URL: https://ia.cr/2024/2035
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2024/2035,
      author = {Ping Wang},
      title = {A Heuristic Proof of P $\neq$ {NP}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/2035},
      year = {2024},
      url = {https://eprint.iacr.org/2024/2035}
}