A Nontrivial Lower Bound for an NP Problem on Automata
Etienne Marc Grandjean · SIAM Journal on Computing · 1990
An NP problem L is linearly NP-complete if each ${\operatorname{NTIME}}(n)$-problem is reducible to L in linear time on a deterministic Turing machine. This implies that $L otin \operatorname{DTIME}(cn)$ for each $c \geqq 1$. Let R.I.S.A. (Reduction of Incompletely Specified Automata) be the following NP-complete problem (quoted AL7 in the classical book [M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979]. INSTANCE: a positive integer K and an incompletely specified deterministic finite state automaton $A = (Q, \Sigma, \delta, q_0, F)$, where $\delta$ is a “partial” transition function from $Q \times \Sigma $ into Q, and $Q, \Sigma, q_0, F$ are defined as usual. QUESTION: Can $\delta$ be extended to a total transition function from $Q \times \Sigma$ into Q in such a way that the resulting completely specified automaton has an equivalent “reduced automaton” with K or fewer states? It is proved that problem R.I.S.A. is linearly NP-complete. The proof uses a notion of generalized spectrum of a first-order sentence, which has the form $\forall y \bigwedge _{i < p} \mathcal{F}_i (y) = \mathcal{G}_i (y)$ where each $\mathcal{F}_i$, $\mathcal{G}_i$ is a word of the form $f_k \cdots f_2 f_1$, $k \geqq 0$, and each f is a unary function symbol.