Review Article Open Access

On a Proof of Inequality of the Classes of Decision Problems P and NP

Abstract

This paper is a new version of three papers presented to the academy of sciences of Turin in 2016 and to the Journal of Computer Science in 2020 and 2022 [1-3]. According to the Journal of Computer Science, more than 6000 readers have “viewed” the two papers published by that journal and more than 1700 readers have downloaded them.

The theorems presented in those papers were based on the equivalence of a deterministic turing machine M processing some input x belonging to {0,1}n with an n-input Boolean circuit Cn, and on the hypothesis that the number of gates, or AND, OR, NOT operators, appearing in circuit Cn, is polynomial in the running time of the corresponding turing machine.

According to some readers that hypothesis of the equivalence “turing machine -boolean circuit” is questionable. The purpose of this paper is to present a new proof of the inequality of P and NP which is not based on this equivalence. Besides, this new paper contains the answers to the questions asked by some readers and the proofs of some theorems which had been omitted for the sake of brevity.

The analysis discussed in this paper and in its previous versions is based on a well-known NP-complete problem which is called “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 paper a proof is presented according which the number of boolean operations 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 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.

Angelo Raffaele Meo*

To read the full article Download Full Article | Visit Full Article