Historical dossier 041

Graph Isomorphism is PSPACE-complete; A Polynomial Time Algorithm for Graph Isomorphism

A recorded P = NP claim by Matthew Delacorte, Reiner Czerwinski, preserved from Woeginger’s frozen 2016 page.

Dossier: 041
Author(s): Matthew Delacorte, Reiner Czerwinski
Date recorded: August 2007; November 2007
Direction: P = NP
Works or versions: 2
Adjudication: Not recorded
Seed source: sources/captures/woeginger-list-frozen-2016.html
Source selector: ol > li:nth-of-type(41)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Equal]: (a) In August 2007, Matthew Delacorte proved that he graph isomorphism problem is PSPACE-complete: http://arxiv.org/abs/0708.4075. His (very short) paper is titled "Graph Isomorphism is PSPACE-complete". This result does not settle the P-versus-NP question, but it does imply NP=PSPACE. (b) In November 2007, Reiner Czerwinski proved that the graph isomorphism problem is polynomially solvable: http://arxiv.org/abs/0711.2010. The paper is titled "A Polynomial Time Algorithm for Graph Isomorphism"; it proposes an algorithm that has polynomial complexity, and constructively supplies the evidence that graph isomorphism lies in P. In combination, the two results in (a) and (b) imply that P=PSPACE, which of course yields P=NP as a corollary. (Thanks to Marcus Ritt for providing the link to Delacorte, and thanks to Jan van Leeuwen for providing the link to Czerwinski.)

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
Live
http://arxiv.org/abs/0708.4075
200 · Link status checked 24 July 2026.
Link printed in the historical dossier
Live
http://arxiv.org/abs/0711.2010
200 · Link status checked 24 July 2026.

Cite this dossier

Plain text

The P versus NP Register. “Dossier 041: Graph Isomorphism is PSPACE-complete; A Polynomial Time Algorithm for Graph Isomorphism.” As of 24 July 2026.

BibTeX

@misc{pvnp-register-041-2026,
  author = {{The P versus NP Register}},
  title = {Graph Isomorphism is PSPACE-complete; A Polynomial Time Algorithm for Graph Isomorphism},
  year = {2026},
  note = {Dossier 041; as of 2026-07-24}
}

Event timeline

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