Historical dossier 002

Polynomial-Time Partition of a Graph into Cliques

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

Dossier: 002
Author(s): Anatoly Plotnikov
Date recorded: 1996
Direction: P = NP
Works or versions: 1
Adjudication: Not recorded
Seed source: sources/captures/woeginger-list-frozen-2016.html
Source selector: ol > li:nth-of-type(2)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Equal]: The 1996 issue (Volume 1, 1996, pp. 16-29) of the "SouthWest Journal of Pure and Applied Mathematics" (SWJPAM) contains the article "Polynomial-Time Partition of a Graph into Cliques" by the Ukrainian mathematician Anatoly Plotnikov. This article designs a polynomial time algorithm for an NP-hard graph problem, and thus proves P=NP. (SWJPAM is an electronic journal devoted to all aspects of Pure and Applied mathematics, and related topics. Authoritative expository and survey articles on subjects of special interest are also welcomed. SWJPAM serves as an international forum for the publication of high-quality strictly peer-reviewed original research articles. The article is usually sent to at least two experts in the area. Two positive reviews are required for the acceptance and publication of any submitted article.)

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.emis.de/journals/SWJPAM/vol1-96.html
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
Dead
http://www.emis.de/journals/SWJPAM/
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
Dead
http://www.emis.de/journals/SWJPAM/Vol1_1996/plotnikov.ps
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
Dead
http://www.vinnica.ua/~aplot/
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 002: Polynomial-Time Partition of a Graph into Cliques.” As of 24 July 2026.

BibTeX

@misc{pvnp-register-002-2026,
  author = {{The P versus NP Register}},
  title = {Polynomial-Time Partition of a Graph into Cliques},
  year = {2026},
  note = {Dossier 002; as of 2026-07-24}
}

Event timeline

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