Research Article Open Access

On a Proof of Inequality of PvsNP

Angelo Raffaele Meo1
  • 1 Department of Computer Science, Politecnico di Totino, Italy

Abstract

This study is a new version of a previous paper. Its purpose is to simplify some sections of the old version and, above all, to present the proofs of some theorems which had been omitted for the sake of brevity. The analysis discussed in this study and its previous version is based on a well-known NP-complete problem which is called the "satisfiability problem" or "SAT". From SAT a new NP-complete problem, called "core function", derives; this problem is described by a Boolean function of the number of the clauses of SAT. In this study, a new proof is presented according to which the number of gates of the minimal implementation of core function increases with n exponentially. Since the synthesis of the core function is an NP-complete problem, this result can be considered as the proof of the theorem which states that the class P of all the decision problems which can be solved in polynomial time does not coincide with the class NP of the problems for which an answer can be verified in polynomial time.

Journal of Computer Science
Volume 19 No. 1, 2023, 87-98

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

Submitted On: 23 January 2022 Published On: 16 January 2023

How to Cite: Meo, A. R. (2023). On a Proof of Inequality of PvsNP. Journal of Computer Science, 19(1), 87-98. https://doi.org/10.3844/jcssp.2023.87.98

  • 2,010 Views
  • 559 Downloads
  • 0 Citations

Download

Keywords

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