Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes
I will give a general algorithm going through intermediate steps that can be implemented in polynomial time, each. Yet, I will not dive into the details of how to implement each step. The solution I'm suggesting may not be optimal, yet it is easy to understand. Essentially, we're going to rely on basic properties of Pushdown automata (PDAs, for short).
Let $\mathcal{A}$ be a given DFA over the alphabet $\Sigma$, and consider the language $PAL\subseteq \Sigma^*$ of the palindrome words. We need to decide whether $L(\mathcal{A})\subseteq PAL$ in polynomial time. Note that $L(\mathcal{A})\subseteq PAL$ iff $L(\mathcal{A})\cap \overline{PAL} = \emptyset$. So we need to decide whether the language $L(\mathcal{A})\cap \overline{PAL}$ is empty, and we do it as follows:
1- Construct a PDA $\mathcal{B}$ for $\overline{PAL}$: this is a well known exercise.
2- Construct a PDA $\mathcal{C}$ for $L(\mathcal{A})\cap \overline{PAL}$: this is also known, and can be done in polynomial time by a product construction of $\mathcal{A}$ and $\mathcal{B}$ (for example, see here).
3- Finally, check whether the language of the PDA $\mathcal{C}$ is empty. This also can be done in polynomial time (see here, or here).