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

CREATORDaniel Alexander Spenner
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.07031

Browse the full library · About the Tower of Babel