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

Journal of computer sciences

article

Angelo Raffaele Meo¹ 

[1] Accademia delle Scienze di Torino

关键词: P-NP Question;    Complexity;    Boolean Functions;    Satisfiability;    Polynomial or Exponential Increase;   

DOI  :  10.3844/jcssp.2021.511.524

学科分类：计算机科学（综合）

来源: Science Publications

【 摘 要 】

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.

【 授权许可】

CC BY