HackerPapers

arXiv:0810.5056cs.CC

P is not equal to NP

Sten-Ake Tarnlund

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

SAT is not in P, is true and provable in a simply consistent extension B' of a first order theory B of computing, with a single finite axiom characterizing a universal Turing machine. Therefore, P is not equal to NP, is true and provable in a simply consistent extension B" of B.

arXiv comments
In the 2nd printing the proof, in the 1st printing, of theorem 1 is divided into three parts a new lemma 4, a new corollary 8, and the remaining part of the original proof. The 2nd printing contains some simplifications, more explanations, but no error has been corrected
Journal reference
DOI
Subjects
cs.CCComputational Complexity cs.LOLogic in Computer Science

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Oct 2008 to Oct 2008. 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.