Optimal Chain Density and Space-Time Tradeoffs for the TSP
The paper nearly settles the tradeoff between the size of a set system over and its number of full chains, an extremal question raised by Johnson, Leader and Russell as a counterpart to Sperner-type results, and linked by recent work to the space and time complexity of Bellman–Held–Karp dynamic programming for permutation problems.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-assisted
- Method
- Argument
- Field
- Extremal Set Theory, Algorithms
- Posed by
- Johnson, Leader and Russell
- Year posed
- 2015
- Years open
- 11y
- Solved
- 2026-07-13
- Model
- ChatGPT 5
- Vendor
- OpenAI
- Collaborators
- Alexandr Andoni, Justin Dallant, László Kozma, Hantao Yu
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
The authors describe the tradeoff as nearly settled rather than settled.
What the AI did
The disclosure is one sentence: the results of the paper were obtained with the help of ChatGPT 5. It says the results rather than the exposition, but does not say how much, so the lowest tier applies.
Verification
No independent review, and the single-sentence disclosure does not separate the model's contribution from the authors'. Preprint, not refereed.