HackerPapers

arXiv:1208.0954cs.CC

P = NP

Sergey V. Yakhontov

Abstract

The present work proves that P=NP. The proof, presented in this work, is a constructive one: the program of a polynomial time deterministic multi-tape Turing machine M_ExistsAcceptingPath, that determines if there exists an accepting computational path of a polynomial time non-deterministic single-tape Turing machine M_NP, is constructed (machine M_ExistsAcceptingPath is different for each Turing machine M_NP). Machine M_ExistsAcceptingPath is based on reduction to problem LP (linear programming) instead of reduction to problem 3-CNF-SAT which is commonly used. In more detail, machine M_AcceptingPath uses a reduction of the initial string problem to another string problem TCPE (defined in the paper) that is NP-complete and decidable in polynomial time. The time complexity of machine M_ExistsAcceptingPath is O(t(n)^{272}) wherein t(n) is an upper bound of the time complexity of machine M_NP.

arXiv comments
63 pages. All the known errors corrected; fixes are in linear equations (X,X) (subsection 4.4), connector graph linear equations (subsection 4.5), and in linear program TCPEPLP itself (subsection 4.6); it seems a complete solution
Journal reference
DOI
Subjects
cs.CCComputational Complexity

On Hacker News

Linked by 3 identifiable commenters in 3 comments across 2 threads, from Dec 2013 to Dec 2013. Found in 2 HN submissions from Dec 2013 to Dec 2013. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. P = NP 2 comments

    • Some context would be helpful. Is the a credible computer scientist, or just another crackpot? What has been the response of the mathematical community to this? What, if any, are the criticisms of it? It looks like there have been a number of versions of this paper since last…

      fishtoasterView on HNParent context

    • [Meta: please submit the direct link, not a link-shortened version] This arXiv paper[1] is apparently from 2012. A good meta-resource and summary of attempts on P ?= NP, including this one, can be found at [2]. From [2]: > Among all these papers, there is only a single paper…

      saidajigumiView on HNParent context

  2. P = NP [pdf] 1 comment

    • A note -- when linking to arXiv, please link to the abstract[1], not directly to the PDF. The abstract has other information about the paper, and one can see different versions of the paper, and of course one can click through to the actual paper. Going the other way requires…

      SniffnoyView on HNParent context

Submitted to Hacker News

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