Historical dossier 105

P not equal NP by modus tollens

A recorded P ≠ NP claim by Joonmo Kim, preserved from Woeginger’s frozen 2016 page.

Dossier: 105
Author(s): Joonmo Kim
Date recorded: March 2014
Direction: P ≠ NP
Works or versions: 2
Adjudication: Recorded
Seed source: sources/captures/woeginger-list-frozen-2016.html
Source selector: ol > li:nth-of-type(105)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Not equal]: In March 2014, Joonmo Kim proved that P is not equal to NP. The proof uses an artificially designed Turing Machine that generates the instances of the satisfiability problem, and checks their satisfiability. Under the assumption P equal NP, this machine has a certain property, which it does not have without the assumption. This leads to P not equal NP, by modus tollens. The paper "P not equal NP by modus tollens" is available at http://arxiv.org/abs/1403.4143. In April 2014, Dan Hassin, Adam Scrivener and Yibo Zhou note that the logic that Kim uses is inconsistent and provide evidence that the proof is invalid. Their findings are available at http://arxiv.org/abs/1404.5352. (Thanks to Szabolcs Ivan for providing these links.)

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

Cite this dossier

Plain text

The P versus NP Register. “Dossier 105: P not equal NP by modus tollens.” As of 24 July 2026.

BibTeX

@misc{pvnp-register-105-2026,
  author = {{The P versus NP Register}},
  title = {P not equal NP by modus tollens},
  year = {2026},
  note = {Dossier 105; as of 2026-07-24}
}

Event timeline

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