Historical dossier 023

Complexity Theory for Simpletons; Complexity science for simpletons

A recorded P ≠ NP claim by Craig Alan Feinstein, preserved from Woeginger’s frozen 2016 page.

Dossier: 023
Author(s): Craig Alan Feinstein
Date recorded: July 2005; July 2006
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(23)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Not equal]: In July 2005, Craig Alan Feinstein wrote the paper "Complexity Theory for Simpletons". This paper explains why P is not equal to NP in the so-called Mabel-Mildred-Feinstein model of computation. The paper also kind of settles the Collatz 3n+1 Conjecture: Every valid proof in the Feinstein-model-of-proof must have an infinite number of lines. A similar statement is shown to hold for the Riemann Hypothesis. Another version of this paper appeared under the titel "Complexity science for simpletons" in Progress in Physics, July 2006. Progress in Physics claims to be a quarterly, peer-reviewed scientific journal of advanced studies in theoretical and experimental physics, including related themes from mathematics. (Thanks to Clyde P. Kruskal 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
Live
http://arxiv.org/abs/cs.CC/0507008
200 · Link status checked 24 July 2026.
Link printed in the historical dossier
Dead
http://www.encyclopedia.com/doc/1G1-149317859.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.encyclopedia.com/Progress+in+Physics/publications.aspx?pageNumber=1
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 023: Complexity Theory for Simpletons; Complexity science for simpletons.” As of 24 July 2026.

BibTeX

@misc{pvnp-register-023-2026,
  author = {{The P versus NP Register}},
  title = {Complexity Theory for Simpletons; Complexity science for simpletons},
  year = {2026},
  note = {Dossier 023; as of 2026-07-24}
}

Event timeline

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