An optimal, deterministic, polynomial time sorting adversary
A sorting adversary answers the comparisons of a sorting algorithm online and is legal if every finite sequence of its answers is consistent with some total order. Atallah and Kosaraju (1981) gave an efficient deterministic adversary forcing every correct sorter to make comparisons, and Kaplan, Zamir and Zwick (SODA 2019) raised this to . Kaplan, Zamir and Zwick ask whether an efficient (polynomial-time) deterministic adversary can force comparisons for every and all sufficiently large , matching the information-theoretic bound. Does one exist?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Theoretical computer science
- Posed by
- Haim Kaplan, Or Zamir and Uri Zwick, The amortized cost of finding the minimum (SODA 2015), Section 7, as cited by the manuscript
- Year posed
- 2015
- Years open
- 11y
- Solved
- 2026-11-06
- Model
- GPT 6 Astra (Codex)
- Vendor
- OpenAI
- Collaborators
- Nicholas Nash
- Verification
- Lean-checked, statement unaudited
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: there is a deterministic legal adversary, initialized using only , that uses polynomially many bit operations per query and forces every correct sorter to make at least comparisons. Previous efficient deterministic adversaries forced (Atallah and Kosaraju 1981) and (Kaplan, Zamir and Zwick 2019). Polynomial time is proved in Lean in an explicit arithmetic cost model (a counted primitive-operation charge on exact rationals), not as an instruction-level bound for a machine model, and the degrees are enormous. The paper also derives consequences for sorting under partial information and partial order production.
What the AI did
Per the paper's methodological disclosure, the adversary and its analysis are due to AI (GPT 6 Astra, run in Codex with the optimal adversary as the goal; about 27 hours according to the submission). The human author shaped the exposition and abstractions and reviewed the paper except for the appendices, which are marked as raw AI-generated work. The Lean formalization is part of the same project.
Verification
No independent mathematician has checked this yet. Checked here on 15 November 2026: the paper's introduction and disclosure (Hexagon 2611.00196v2, sole author Nicholas Nash, ORCID-linked), and the Lean repository nicknash/sorting-adversary-proofs at commit 0a46d06 (12 Nov 2026, Lean 4.33.1). The headline SortingAdversary.Continuous.UniformEfficient.asymptoticallyOptimal_and_polynomial was read with the definitions it rests on: DecisionTree.Correct (every ranking recovered), legality (every run consistent with some ranking), and for every delta > 0 a lower bound of (1 - delta) n log2 n comparisons for all large n, plus fixed polynomial charges for initialization and every reachable query in the project's own arithmetic cost model. A grep of the Lean sources found no sorry, admit or axiom declarations; native_decide appears only in the older StrengthenedCurvature development, outside the headline. The project's CI run 43209728075 on that commit passed the placeholder check, full build, leanchecker replay and an all-declaration axiom audit of the continuous development allowing only propext, Classical.choice and Quot.sound. Not rebuilt here. The paper's appendices are unreviewed AI output by the author's own statement.
Sources
Submitted by SwiftRaven874 on