Deciding DFA-Primality is NP -Hard
Daniel Alexander Spenner · 2026
Read Deciding DFA-Primality is NP -Hard by Daniel Alexander Spenner (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-07031.txt.
Description
Spenner settles a long open hardness question about deterministic finite automata, the simple state machines that read strings and accept or reject them. A machine is composite when several strictly smaller machines, combined by intersection, decide exactly the same language. It is prime when no such combination exists. Deciding which case holds, the Prime-DFA problem, was known since 2015 only to be NL hard and inside ExpSpace, a doubly exponential gap in difficulty.
The author closes that gap by proving the problem NP hard, using a reduction from propositional satisfiability, the classic problem of deciding whether a logical formula can be made true. The proof rests on a detailed characterisation of primality. It covers a class of automata broad enough to include every machine the reduction can produce. It is the first progress on the problem's complexity since its definition.
Catalog record
| CREATOR | Daniel Alexander Spenner |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 147 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.07031