Probabilistic Automatic Complexity Is At Most Three
Gill introduced the probabilistic automatic complexity of a string: the least number of states of a probabilistic finite automaton for which is the unique most probably accepted string of its length. He asked whether is unbounded, no string with being known. The paper proves for every string over every finite alphabet, with an explicit three-state witness.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Construction
- Field
- Automata Theory, Descriptional Complexity
- Posed by
- Christopher Gill
- Year posed
- 2024
- Years open
- 2y
- Solved
- 2026-07-28
- Model
- Claude Fable 5
- Vendor
- Anthropic
- Collaborators
- Bjørn Kjos-Hanssen
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 10 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The author states the construction was found in conversation with, and verified with the assistance of, Claude Fable 5, and that the proof was formalized in Lean with assistance from Harmonic's Aristotle.
Verification
No independent review. A Lean formalization is reported but no artifact was located to check, so this does not carry the Lean-verified tier. Preprint, not refereed.