Historical dossier 009

Consequences of an exotic definition for P=NP

A recorded Other claim by N.C.A. da Costa, F.A. Doria, preserved from Woeginger’s frozen 2016 page.

Dossier: 009
Author(s): N.C.A. da Costa, F.A. Doria
Date recorded: 2003
Direction: Other
Works or versions: 3
Adjudication: Recorded
Seed source: sources/captures/woeginger-list-frozen-2016.html
Source selector: ol > li:nth-of-type(9)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Unprovable]: The journal "Applied Mathematics and Computation" (AMC) addresses work at the interface between applied mathematics, numerical computation, and applications of systems-oriented ideas to the physical, biological, social, and behavioral sciences, and emphasizes papers of a computational nature focusing on new algorithms, their analysis and numerical results. Applied Mathematics and Computation 145 (2003), pp. 655-665, contains the article "Consequences of an exotic definition for P=NP" by N.C.A. da Costa and F.A. Doria. This article shows that "P-not-equal-to-NP" is unprovable in ZFC. Here is a review of this proof by the German logician Ralf Schindler. Andreas Blass, the reviewer of this paper in the AMS Mathematical Reviews, writes in his review MR2009291 (2004f:03076): "The authors claim to prove (Corollary 4.6) that, if ZFC is consistent, then it remains so when P=NP is added as an additional axiom. Unfortunately, there is an error in the proof [...]."

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
Dead
http://www.elsevier.com/locate/amc
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://dx.doi.org/10.1016/S0096-3003(03)00176-0
200 · Link status checked 24 July 2026.
Link printed in the historical dossier
Dead
http://wwwmath.uni-muenster.de/math/inst/logik/org/staff/rds/review.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://wwwmath.uni-muenster.de/math/inst/logik/org/staff/rds/
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 009: Consequences of an exotic definition for P=NP.” As of 24 July 2026.

BibTeX

@misc{pvnp-register-009-2026,
  author = {{The P versus NP Register}},
  title = {Consequences of an exotic definition for P=NP},
  year = {2026},
  note = {Dossier 009; as of 2026-07-24}
}

Event timeline

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