HackerPapers

arXiv:cs/0610125cs.CC

Report on article: P=NP Linear programming formulation of the Traveling Salesman Problem

Radoslaw Hofman

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

This article presents counter examples for three articles claiming that P=NP. Articles for which it applies are: Moustapha Diaby "P = NP: Linear programming formulation of the traveling salesman problem" and "Equality of complexity classes P and NP: Linear programming formulation of the quadratic assignment problem", and also Sergey Gubin "A Polynomial Time Algorithm for The Traveling Salesman Problem"

arXiv comments
This version contain more figures, and clearer way to explain counter example idea for k dimensions
Journal reference
DOI
Subjects
cs.CCComputational Complexity cs.DMDiscrete Mathematics cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Jan 2023 to Jan 2023.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. “P = NP” Polynomial-Sized LP Models for Hard Cops 1 comment

    • I see article here which directly criticizes the whole approach while giving counterexamples for original (2006 version) of the paper: https://arxiv.org/abs/cs/0610125 Have the authors made any attempt to address this criticism?

      ghordynskiView on HNParent context

Submitted to Hacker News

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