I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given a 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 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 (_not_ states, as in the Sipser problem), 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).

I also 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?