Having a better complexity / adversary argument for finding if a finite automata accepts a palindrome
You can solve this in $O(n^2)$, where $n$ is the number of states in the original DFA (or NFA), using your idea. Compute the product automaton of the original automaton and its reverse. The new automaton contains $O(n^2)$ states. As to the number of edges, in the original DFA, each state has $|\Sigma|$ outgoing edges, and in its reverse, there are $|\Sigma|n$ transitions overall. Let us denote by $a(q)$ the number of outgoing transitions from $q$ in the original DFA, and by $b(q)$ the number in the reverse DFA. Using $Q$ for the set of states, the total number of transitions in the product automaton is
$$
\sum_{q_1,q_2 \in Q} a(q_1) b(q_2) =
\sum_{q_1,q_2 \in Q} |\Sigma| b(q_2) =
|\Sigma| n \sum_{q_2 \in Q} b(q_2) =
|\Sigma|^2 n^2.
$$
Assuming $|\Sigma|$ is constant, this is $O(n^2)$.
Now check whether some final state is reachable from some initial state, using BFS/DFS, in  time $O(n^2)$.

We can prove an essentially matching lower bound given SETH. Recall that SETH states that for every $\epsilon &gt; 0$ there is $k$ such that $k$-SAT cannot be solved in time $O(2^{(1-\epsilon) n})$, where $n$ is the number of variables. We will show how to reduce $k$-SAT to your problem.

Given a $k$-SAT formula $\phi$ with $n$ variables and $m = O(n^k)$ clauses, consider the following language $L$ of all words of the form $\alpha x \beta \gamma y \delta$, where:


$|\alpha| = |\beta| = |\gamma| = |\delta| = n/2$, $|x| = |y| = m$.
We think of $\alpha$ as an assignment for the first $n/2$ variables. If $x_i = 0$ then $\alpha$ must satisfy the $i$th clause.
We think of $\beta$ as an assignment for the last $n/2$ variables. If $y^R_i = y_{m+1-i} = 1$ then $\beta$ must satisfy the $i$th clause.


Any word in $L \cap L^R$ must be of the form $\alpha x \beta \beta^R x^R \alpha^R$, and so by construction $\alpha\beta$ satisfies $\phi$. Conversely, if $\alpha\beta$ satisfies $\phi$, then we can choose $x$ so that the corresponding word is in $L \cap L^R$, Hence $\phi$ is satisfiable iff $L \cap L^R$ is non-empty.

How many states do we need to accept $L$? We can read and store $\alpha$ using $O(2^{n/2})$ many states. Therefore using $O(2^{n/2} m)$ states, we can verify the second condition (on $\alpha x$). Similarly, we can verify the third condition (on $\beta y$) using $O(2^{n/2} m)$ more states. Verifying the first condition takes $O(n+m)$ more states, for a grand total of $O(2^{n/2} m) = O(2^{n/2 + o(1)})$ states.

If your problem could be solve in time $O(N^{2-\delta})$ (where $N$ is the number of states in the input automaton), then we would get an algorithm for $k$-SAT running in time $O(2^{(1-\delta/2)n + o(1)})$, and so obtain a contradiction if $\delta/2 \geq \epsilon$. This shows that assuming SETH, your problem cannot be solved in $O(N^{2-\delta)}$ for any $\delta &gt; 0$.