Research Article Open Access

On the P VS NP Question: A New Proof of Inequality

Angelo Raffaele Meo1
  • 1 Accademia delle Scienze di Torino, Italy

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.

Journal of Computer Science
Volume 17 No. 5, 2021, 511-524

DOI: https://doi.org/10.3844/jcssp.2021.511.524

Submitted On: 23 September 2020 Published On: 27 May 2021

How to Cite: 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

  • 113 Views
  • 66 Downloads
  • 0 Citations

Download

Keywords

  • P-NP Question
  • Complexity
  • Boolean Functions
  • Satisfiability
  • Polynomial or Exponential Increase