In fact, it is the complement of the equivalence problem, i.e., the problem whether two given acyclic NFAs are inequivalent, that is NP-complete. This is described in the "Elements of the Theory of Computation" by Lewis and Papadimitriou, second edition. The inequivalence problem for *-free regular expressions is proved to be NP-complete in theorem 7.3.8, and the NP-completeness of the corresponding problem for acyclic NFAs is given as problem 7.3.7.
The certificate of inequivalence for NFAs and is a string from . Since the automata are acyclic, the length of words they accept does not exceed the number of states.
To prove that inequivalence of NFAs is NP-hard, we can reduce SAT to inequivalence of *-free regular expressions and then to that of automata. As described in p. 103 of the book, converting a regular expression into an equivalent NFA takes polynomial time (this is seen by examining the proof of the theorem about the equivalence of regular expressions and NFAs). One needs to make sure that *-free expressions produce acyclic automata.
The idea of the reduction of SAT is the following. Given a Boolean formula in CNF, generate two regular expressions and . If the Boolean formula has variables, then where
Then is the set of all truth assignments that fail to satisfy , so is the set of assignments that make the Boolean formula false.