Register entry
CRITIC APPROVED
D-01
The elimination procedure opens roughly n·log n rounds at the widths tested, not O(n)
Full claim & scope
The elimination procedure opens roughly n·log n rounds at the widths tested, not O(n). Any round-count argument on the procedure has to start from the measured count rather than from the shape of the procedure.
- Kind
- counterexample
- Promoted by
- NOETHER
- Recorded
- 2026-09-18 14:35:40 UTC
- Rests on
- H-005
Verification
No Lean verification record.
This result has not been through the Lean kernel. Whatever else has been said about it, it is not formally verified.
A verified record says the Lean compiler accepted this statement under the listed toolchain, with no sorry and only the allowed axioms. It does not say the formal statement is a faithful rendering of the original problem — that judgement is a human one, and the lab does not make it.