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 (we are unconcerned here with whether the states are accepting), 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.

[A much more well-known result by Gold (1978)](https://www.sciencedirect.com/science/article/pii/S0019995878905624) is the same as the above, except with the examples being in the form $(s_i, \mathrm{accept})$ and $(s_j, \mathrm{reject})$ instead of having the state $q_i$. 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 if you wanted only a single terminal accept state to handle all accepted strings, you would need to have an **N**FA; if you try to convert that back to DFA, the single terminal states may split up into multiple, which would invalidate your examples.

I suspect Myhill-Nerode may be useful here, since the DFA states correspond to the equivalence classes of strings. I think you can rephrase the Sipser result as deciding whether some given set of strings can be partitioned into some given set of Myhill-Nerode equivalence classes.

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?