HackerPapers

arXiv:1802.05484cs.CC

On the P vs NP question: a proof of inequality

Angelo Raffaele Meo

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

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.

arXiv comments
Journal reference
DOI
Subjects
cs.CCComputational Complexity

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Feb 2018 to Feb 2018. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.