  Nondeterministic automata may be viewed as succinct programs implementing
deterministic automata, i.e. complete specifications. Converting a given
deterministic automaton into a small nondeterministic one is known to be
computationally very hard; in fact, the ensuing decision problem is
PSPACE-complete. This paper stands in stark contrast to the status quo. We
restrict attention to subatomic nondeterministic automata, whose individual
states accept unions of syntactic congruence classes. They are general enough
to cover almost all structural results concerning nondeterministic
state-minimality. We prove that converting a monoid recognizing a regular
language into a small subatomic acceptor corresponds to an NP-complete problem.
The NP certificates are solutions of simple equations involving relations over
the syntactic monoid. We also consider the subclass of atomic nondeterministic
automata introduced by Brzozowski and Tamm. Given a deterministic automaton and
another one for the reversed language, computing small atomic acceptors is
shown to be NP-complete with analogous certificates. Our complexity results
emerge from an algebraic characterization of (sub)atomic acceptors in terms of
deterministic automata with semilattice structure, combined with an equivalence
of categories leading to succinct representations.
