Historical dossier 001

P=NP

A recorded P = NP claim by Ted Swart, preserved from Woeginger’s frozen 2016 page.

Dossier: 001
Author(s): Ted Swart
Date recorded: 1986/87
Direction: P = NP
Works or versions: 3
Adjudication: Recorded
Seed source: sources/captures/woeginger-list-frozen-2016.html
Source selector: ol > li:nth-of-type(1)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Equal]: In 1986/87 Ted Swart (University of Guelph) wrote a number of papers (some of them had the title: "P=NP") that gave linear programming formulations of polynomial size for the Hamiltonian cycle problem. Since linear programming is polynomially solvable and Hamiltonian cycle is NP-hard, Swart deduced that P=NP. In 1988, Mihalis Yannakakis closed the discussion with his paper "Expressing combinatorial optimization problems by linear programs" (Proceedings of STOC 1988, pp. 223-228). Yannakakis proved that expressing the traveling salesman problem by a symmetric linear program (as in Swart's approach) requires exponential size. The journal version of this paper has been published in Journal of Computer and System Sciences 43, 1991, pp. 441-466.

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

Adjudication status

Adjudication recorded

Recorded

This historical dossier records an adjudication in Woeginger’s note. Follow the sources in that note for its basis. The Register has not re-judged it.

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
Live
http://dx.doi.org/10.1016/0022-0000(91)90024-Y
200 · Link status checked 24 July 2026.

Cite this dossier

Plain text

The P versus NP Register. “Dossier 001: P=NP.” As of 24 July 2026.

BibTeX

@misc{pvnp-register-001-2026,
  author = {{The P versus NP Register}},
  title = {P=NP},
  year = {2026},
  note = {Dossier 001; as of 2026-07-24}
}

Event timeline

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