On the P VS NP Question: A New Proof of Inequality
Angelo Raffaele Meo1 Show affiliations
- Accademia delle Scienze di Torino, Italy
Journal of Computer Science, Volume 17, Issue 5, pp. 511–524 · doi.org/10.3844/jcssp.2021.511.524
Abstract
The analysis discussed in this study is based on a well-known NP-complete problem which is called “satisfiability problem or SAT”. From SAT a new NP-complete problem derives, which is described by a Boolean function of the number n of the clauses of SAT called “core function”. In this study a new proof is presented according which the number of gates of the minimal implementation of core function increases with n exponentially. Since the synthesis of core function is an NP-complete problem, this result can be considered as the proof of the theorem according which P and NP do not coincide.
Licence and reuse
Open access. This article is licensed under a Creative Commons Attribution 4.0 International Licence (CC BY 4.0), as printed on the article, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original authors and the source. No permission is needed.
How to reuse this articleResponses (0)
About this article
Meo, A. R. (2021). On the P VS NP Question: A New Proof of Inequality. Journal of Computer Science, 17(5), 511–524. https://doi.org/10.3844/jcssp.2021.511.524
- Licence
- CC BY 4.0
- Issue
- Volume 17, Issue 5
- Policies
- Editorial independenceUse of generative AIData availabilityAppeals and complaints
- Version
- Version of record