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

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.