Historical dossier 022

Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P?

A recorded P ≠ NP claim by Bhupinder Singh Anand, preserved from Woeginger’s frozen 2016 page.

Dossier: 022
Author(s): Bhupinder Singh Anand
Date recorded: June 2005
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(22)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Not equal]: In June 2005, Bhupinder Singh Anand proved that P is not equal to NP, under the assumption that every Turing-decidable true arithmetical relation is provable in Peano Arithmetic. His paper is called "Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P?", and it is available as pdf-file from math.GM/0506126. The paper shows that (under a provability assumption as above) Goedel's arithmetical predicate R(x), treated as a Boolean function, is in the complexity class NP, but not in P. (Another interesting result in this paper states that the Halting problem is effectively solvable, albeit not algorithmically.) (Thanks to Ugo Vaccaro for providing this link.)

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://xxx.lanl.gov/pdf/math.GM/0506126
DEAD:URLError · 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://xxx.lanl.gov/abs/math.GM/0506126
DEAD:URLError · 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 022: Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P?.” As of 24 July 2026.

BibTeX

@misc{pvnp-register-022-2026,
  author = {{The P versus NP Register}},
  title = {Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P?},
  year = {2026},
  note = {Dossier 022; as of 2026-07-24}
}

Event timeline

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