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.
Author
(s) Details
Angelo Raffaele Meo
Accademia Delle Scienze di Torino, Politecnico di Torino, Italy.
Please see the book here:- https://doi.org/10.9734/bpi/mcscd/v9/3100
No comments:
Post a Comment