pith. sign in

arxiv: 1802.05484 · v1 · pith:IET6PHQPnew · submitted 2018-02-15 · 💻 cs.CC

On the P vs NP question: a proof of inequality

classification 💻 cs.CC
keywords functionproblemcorenp-completecalledanalysisbooleancoincide
0
0 comments X
read the original abstract

The analysis discussed in this paper is based on a well-known NP-complete problem which is called satisfiability problem or SAT. From SAT a new NP-complete problem is derived, which is described by a Boolean function called core function. In this paper it is proved that the cost of the minimal implementation of core function increases with n exponentially. Since the synthesis of core function is an NP-complete problem, this result is equivalent to proving that P and NP do not coincide.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.