A New Proof of the Inequality Between P and NP Using the Core Function Framework

This paper contains a new proof of inequality of the classes of decision problems “P” and NP”. Its author had already proposed a different proof in three papers presented to the Academy of Sciences of Turin in 2016 and to the Journal of Computer Science in 2020 and 2022 (Ref [1]), (Ref [2]), (Ref [3]).

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 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.