Counting Linear Extensions Below the Barrier
Koivisto asked at Dagstuhl in 2013 whether the linear extensions of an arbitrary -element poset can be counted exactly in time for some . Yes: a deterministic exact algorithm runs in , breaking the barrier for the general problem.
- Result
- Proved
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Exact exponential algorithms
- Posed by
- Mikko Koivisto, at Dagstuhl
- Year posed
- 2013
- Years open
- 13y
- Solved
- 2026-08-19
- Model
- Claude Opus 5, ChatGPT 5.6 Sol
- Vendor
- Anthropic, OpenAI
- Collaborators
- Keigo Oka
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 28 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The paper's disclosure: "The core mathematical ideas underlying the new part of the algorithm and proof were discovered by Claude Opus 5 (Anthropic) during AI-assisted mathematical exploration" - naming the first-upper-element pattern representation, multiplicity-profile decoding, the deadline dynamic program and the state-counting strategy of Sections 3 to 5. The chain-partition bound of Section 2 refines Kozma and is not new. The research prompt supplied to Claude Opus 5 was itself generated by ChatGPT 5.6 Sol, modelled on OpenAI's publicly released prompt for their cycle double cover work.
Verification
Checked by this site on 21 August 2026 against the paper (arXiv:2608.19505v1): the disclosure is verbatim as quoted and Koivisto's Dagstuhl 2013 question is cited in the abstract. This is an exact deterministic algorithm with a proved worst-case bound, not a heuristic, so it clears the methodology's exclusion. The ancillary Python script cross-checks correctness against brute force on small posets and does not certify the running time; it was not re-run here. Days-old preprint, no independent review.