Exact versus unique nondeterministic automatic complexity

Bjørn Kjos-Hanssen, Travis Rivera Petit

The exact nondeterministic automatic complexity $A_{Ne}(x)$ of a word $x$ is the minimum number of states of a nondeterministic finite automaton that accepts $x$ and no other word…