How many DFAs accept two given strings? Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected, minimal, or non-degenerate ones); thus, $|DFA(n)| = n^{2n}2^n$.

Now consider two strings $x,y\in\Sigma^*$ and define $K(x,y)$ to be the number of elements of $DFA(n)$ that accept both $x$ and $y$.

Question: What is the complexity of computing $K(x,y)$?

This question has implications for machine learning.

Edit: Now that there's a bounty on this question, I suppose a bit more precision in the formulation is in order. For $n\ge1$, let $DFA(n)$ be the collection of $n^{2n}2^n$ automata, as defined above. For $x,y\in\{0,1\}^*$, define $K_n(x,y)$ to be the number of automata in $DFA(n)$ that accept both $x$ and $y$. Question: can $K_n(x,y)$ be computed in time $poly(n,|x|,|y|)$?
So the question is pretty brief but very interesting. I suppose that the input is $n$ in unary, and $x$ and $y$ in binary (or we have problems, as pointed out by Kai's answer).

First of all, if you are interested in knowing $K(x,y)$ approximately, then you can just generate a few random DFA's and this will give you (whp) a good approximation. (I wonder if this complexity class has a name.)

Then knowing $K(x,y)$ precisely seems like a tough problem. As pointed out in the comments by a3_nm and Kaveh, the question is equivalent to determining the number of automata for which $x$ and $y$ go to the same state. I will denote the probability that they go to the same state by $p$.

Update: Some of the things I wrote here were not true, now I fixed them.

It is easy to see that $p \ge 1/n$. We have equality, if $x$ is all 0's and $y$ is all zero except for its last bit, which is a 1. Are there other cases? I don't know. If for example $x$ is the empty string and $y=00$, then $p= \frac{n+1}{(n-1)n}$.

To simplify the problem, I even started to think about what happens if $x$ and $y$ are unary. If both are at least $n$ and their difference is divisible by $n!$, then $p=1$. Is there a simple formula for the unary version?