Historical dossier 017

P=NP: Linear Programming Formulation of the Traveling Salesman Problem; linear programming formulation of the QAP (quadratic assignment problem); Linear programming formulation of the vertex colouring problem; Linear programming formulation of the set partitioning problem; Advances in Combinatorial Optimization

A recorded P = NP claim by Moustapha Diaby, Mark H Karwan, preserved from Woeginger’s frozen 2016 page.

Dossier: 017
Author(s): Moustapha Diaby, Mark H Karwan
Date recorded: October 2004; October 2005; 2010; April 2016
Direction: P = NP
Works or versions: 8
Adjudication: Not recorded
Seed source: sources/captures/woeginger-list-frozen-2016.html
Source selector: ol > li:nth-of-type(17)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Equal]: In October 2004, Moustapha Diaby constructed a linear programming formulation for the travelling salesman problem (TSP). His paper is called "P=NP: Linear Programming Formulation of the Traveling Salesman Problem", and it is available at http://www.business.uconn.edu/users/mdiaby/tsplp/. The correctness of Diaby's proof is frequently discussed in the newsgroup comp.theory. In reaction to these discussions in comp.theory, the paper has been revised and clarified many times. A new version of the paper can be found at http://arxiv.org/abs/cs/0609005 (uploaded: 2 Sep 2006). In October 2005, Moustapha Diaby also constructed a linear programming formulation of the QAP (quadratic assignment problem). This yields yet another proof that P=NP. The paper is available at http://www.business.uconn.edu/users/mdiaby/qaplp/. A new version of the paper can be found at http://arxiv.org/abs/cs.CC/0609004 (uploaded: 2 Sep 2006). A version of the QAP paper has been published in the 2006 IMECS Conference Proceedings (ISBN: 988-98671-3-3). This version was also awarded a "Certficate of Merit Award" by the conference organizers (IAENG). In 2010, Moustapha Diaby provided two further proofs for P=NP. His papers Linear programming formulation of the vertex colouring problem and Linear programming formulation of the set partitioning problem give linear programming formulations for two well-known NP-hard problems. Both papers were published in the "International Journal of Operational Research (IJOR)". In April 2016, Moustapha Diaby and Mark H Karwan published the book "Advances in Combinatorial Optimization " with World Scientific Publishers. The book is available at the website http://www.worldscientific.com/worldscibooks/10.1142/9725. The book presents a generalized framework for formulating hard combinatorial optimization problems as polynomial sized linear programs, and hence implies P=NP. (Thanks to Andrea Lodi, Philipp Lucas, Silvano Martello, Patric �sterg�rd, Philippe Schnoebelen, and Ugo Vaccaro for providing some of these links.)

Preserved from the frozen 2016 page. This is the historical layer, not the Register’s voice.

Adjudication status

Unadjudicated

Unadjudicated

No adjudication is recorded in the imported historical dossier.

Unadjudicated does not mean endorsed.

As of 24 July 2026

Links printed in the dossier

Link status checked against the held 24 July 2026 probe. A dead link does not change the claim’s status.

Link printed in the historical dossier
Dead
http://www.business.uconn.edu/users/mdiaby/tsplp/
DEAD:HTTPError · Link status checked 24 July 2026.
Look for an archived copy. A dead link does not change the claim’s status.
Link printed in the historical dossier
Live
http://arxiv.org/abs/cs/0609005
200 · Link status checked 24 July 2026.
Link printed in the historical dossier
Dead
http://www.business.uconn.edu/users/mdiaby/qaplp/
DEAD:HTTPError · Link status checked 24 July 2026.
Look for an archived copy. A dead link does not change the claim’s status.
Link printed in the historical dossier
Live
http://arxiv.org/abs/cs.CC/0609004
200 · Link status checked 24 July 2026.
Link printed in the historical dossier
Live
http://www.inderscience.com/search/index.php?action=record&rec_id=32718
200 · Link status checked 24 July 2026.
Link printed in the historical dossier
Live
http://www.inderscience.com/search/index.php?action=record&rec_id=34067
200 · Link status checked 24 July 2026.
Link printed in the historical dossier
Dead
http://www.worldscientific.com/worldscibooks/10.1142/9725
DEAD:HTTPError · Link status checked 24 July 2026.
Look for an archived copy. A dead link does not change the claim’s status.

Cite this dossier

Plain text

The P versus NP Register. “Dossier 017: P=NP: Linear Programming Formulation of the Traveling Salesman Problem; linear programming formulation of the QAP (quadratic assignment problem); Linear programming formulation of the vertex colouring problem; Linear programming formulation of the set partitioning problem; Advances in Combinatorial Optimization .” As of 24 July 2026.

BibTeX

@misc{pvnp-register-017-2026,
  author = {{The P versus NP Register}},
  title = {P=NP: Linear Programming Formulation of the Traveling Salesman Problem; linear programming formulation of the QAP (quadratic assignment problem); Linear programming formulation of the vertex colouring problem; Linear programming formulation of the set partitioning problem; Advances in Combinatorial Optimization },
  year = {2026},
  note = {Dossier 017; as of 2026-07-24}
}

Event timeline

No post-seed events are recorded for this dossier. Its imported historical record remains unchanged.