Having a better complexity / adversary argument for finding if a finite automata accepts a palindrome

Let $$A$$ be a DFA over a finite alphabet $$\Sigma$$. Find an algorithm that indicates if $$A$$ accepts a palindrome and give the complexity of this algorithm.

Here is my solution:

If we denote $$^t A$$ the transpose of the finite automaton then in order to see if $$A$$ accepts a palindrome we need to look at the product automaton of $$A$$ and $$^t A$$ and find if this product automaton accepts a word. If yes then this is word is a palindrome.

Finding the transpose of a finite automaton takes $$O(|V|)$$ where $$V$$ is the number of transition of our finite automaton. Take the product of $$A$$ and its transpose takes $$O(|V|^2)$$. And looking if an automaton accept a word takes $$O(|V|^{|S|})$$, where $$|S|$$ is the number of states of our finite automaton. So the final complexity I get for the algorithm I described above is: $$O(|V|^{3 + 2|S|})$$

Now my question is:

Is it possible to improve the complexity? And is it possible to give a proof (using I guess adversary argument) to prove that there isn't a better algorithm (in the sense of complexity) to find if a finite automaton 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 > 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:

1. $$|\alpha| = |\beta| = |\gamma| = |\delta| = n/2$$, $$|x| = |y| = m$$.
2. 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.
3. 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 > 0$$.

• I don’t see any $O(1)$ in the answer. – Yuval Filmus Feb 28 at 19:24
• Assuming the alphabet is fixed, the number of transitions only differs from the number of states by a constant factor. – Yuval Filmus Mar 3 at 16:07
• If you have multiple initial states, add a new initial state with epsilon transitions to all of them. – Yuval Filmus Mar 3 at 16:08
• I don't see why the number of transitions only differs from the number of states by a constant. I mean each state can have a transition to every other state in an NFA. And in this case the number of transitions is : $O(n^2)$... and not $O(n)$ – Thinking Mar 3 at 17:21
• This can't really happen since the NFA is not arbitrary – it's obtained from a DFA by reversing all arrows. See my updated answer. – Yuval Filmus Mar 3 at 19:07

You can solve this problem in polynomial time. For simplicity let's assume the DFA has a single accepting state. If it has multiple you can just run this algorithm for each accepting state until you return $$\text{YES}$$ or every accepting state has been unsuccessfully tried and we return $$\text{NO}$$. Let $$\text{goto}(x, s) = y$$ indicate that there is a transition from state $$x$$ to state $$y$$ on symbol $$s$$.

We use a meet in the middle strategy. We have a tuple $$(b, e)$$ where $$b$$ is the state reached from the beginning, and $$e$$ is the state reached from the end.

We build a list of these tuples. Initially we have only one such tuple $$(b, e) = (\text{init}, \text{accept})$$. Then as long as our list has a tuple that hasn't been expanded before, we expand tuple $$(b, e)$$ by adding all $$(b', e')$$ to the list for each possible symbol $$s$$ where $$\text{goto}(b, s) = b'$$ and $$\text{goto}(e', s) = e$$.

We return $$\text{YES}$$ if we have added $$(x, x)$$ to the list, or $$(x, y)$$ where some $$s$$ exists such that $$\text{goto}(x, s) = y$$. The former case indicates an even length palindrome, the latter an odd length palindrome.

Why is this polynomial time? Hint: there are only $$|S|^2$$ possible tuples $$(b, e)$$ we ever need to expand.