I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are strings and $q_i$ are states, then the problem of "deciding whether there exists some $N$-state DFA for which each $s_i$ causes that DFA to end up in state $q_i$" is NP-complete.

This decision problem seems somewhat similar to [a much more well-known result by Gold (1978)](https://www.sciencedirect.com/science/article/pii/S0019995878905624) in which given examples of _accepted_ and _rejected_ strings, the decision of whether there exists a DFA of some specific size is NP-complete. That result is discussed in some other threads, like [this](https://cstheory.stackexchange.com/a/46427/42414), [this](https://cstheory.stackexchange.com/questions/48352/np-completeness-of-finding-minimum-automaton-in-golds-paper), and [this](https://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem).

If I naively try to reduce from the Gold problem to the Sipser problem, I would try to replace all "accept" with a single "terminal" accept state, and same for reject, but that fails because you can only have a single terminal accept state in an NFA; if you try to convert that back to DFA, the single terminal states may split up into multiple, which would invalidate your examples.

The difference between the Gold result and the Sipser result is that Gold's examples only have "accept" or "reject" for each string, while Sipser's examples have the actual DFA state, without any indication of whether the string is accepted or rejected.

I suspect Myhill-Nerode may be useful here, since the DFA states correspond to the equivalence classes of strings.

I searched through the literature, but was not able to find the Sipser result anywhere. What is another decision problem that we can use as a polynomial-time reduction here? Alternatively, is this result derived or discussed anywhere else?