2006/10/20 by Radosław Hofman, Radoslaw Hofman, Hofman, Radoslaw
Computer Science · Decision Sciences · Engineering · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2 #FOS: Computer and information sciences #Optimization and Mathematical Programming #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods #cs.CC #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0610125
This version contain more figures, and clearer way to explain counter example idea for k dimensions
openalex publication_date 2006/10/20 · arxiv created 2006/11/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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"