Historical dossier 092

Integer factorization and Discrete Logarithm problem are neither in P nor NP-complete; Relationship between circuit complexity and symmetry

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

Dossier: 092
Author(s): Satoshi Tazawa
Date recorded: July 2012
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(92)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Not equal]: In July 2012, Satoshi Tazawa proved that P is not equal to NP. The proof establishes that the decision problem version of integer factorization problem is neither in P nor NP-complete. From this result, the conclusion that P is not NP is reached. The paper "Integer factorization and Discrete Logarithm problem are neither in P nor NP-complete" is available at http://arxiv.org/abs/1207.2171. Later versions of this paper carry the title "Relationship between circuit complexity and symmetry". The paper shows that by interpreting a Boolean circuit as a graph, the small number of graph automorphisms and the large number of subgraph automorphisms in the circuit establishes the exponential circuit lower bound for NP-complete problems. As this strategy violates the largeness condition in Natural proof, this result shows that P!=NP without any contradictions to the existence of pseudorandom functions. (Thanks to Adam Scherlis for providing 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/1207.2171
200 · Link status checked 24 July 2026.

Cite this dossier

Plain text

The P versus NP Register. “Dossier 092: Integer factorization and Discrete Logarithm problem are neither in P nor NP-complete; Relationship between circuit complexity and symmetry.” As of 24 July 2026.

BibTeX

@misc{pvnp-register-092-2026,
  author = {{The P versus NP Register}},
  title = {Integer factorization and Discrete Logarithm problem are neither in P nor NP-complete; Relationship between circuit complexity and symmetry},
  year = {2026},
  note = {Dossier 092; as of 2026-07-24}
}

Event timeline

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