Historical dossier 054

Physical portrayal of computational complexity

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

Dossier: 054
Author(s): Arto Annila
Date recorded: June 2009
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(54)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Not equal]: In June 2009, Arto Annila proved that P is not equal to NP. He writes: The state space of a non-deterministic finite automaton is evolving due to the computation itself hence it cannot be efficiently contracted using a deterministic finite automaton that will arrive at a solution in super-polynomial time. The solution of the NP problem itself is verifiable in polynomial time (P) because the corresponding state is stationary. Likewise the class P set of states does not depend on computational history hence it can be efficiently contracted to the accepting state by a deterministic sequence of dissipative transformations. Thus it is concluded that the class P set of states is inherently smaller than the set of class NP. Annila's paper "Physical portrayal of computational complexity" is available at http://arxiv.org/abs/0906.1084. The paper has also been published in the journal ISRN Computational Mathematics 2012 ID: 321372, 1-15, and is available at http://www.isrn.com/journals/cm/2012/321372/. (Thanks to Matti Niemenmaa 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/0906.1084
200 · Link status checked 24 July 2026.
Link printed in the historical dossier
Dead
http://www.isrn.com/journals/cm/2012/321372/
DEAD:TimeoutError · 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 054: Physical portrayal of computational complexity.” As of 24 July 2026.

BibTeX

@misc{pvnp-register-054-2026,
  author = {{The P versus NP Register}},
  title = {Physical portrayal of computational complexity},
  year = {2026},
  note = {Dossier 054; as of 2026-07-24}
}

Event timeline

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