Existence of an algorithm I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting the letters of w.

Would appreciate any help.
A language $L$ is said to be commutative if the following property holds:


  for every  word $a_1 \dotsm a_n \in L$ and any permutation $\sigma$ on
  $\{1, \ldots, n\}$, the word $a_{\sigma(1)} \dotsm a_{\sigma(n)}$ is
  also in $L$.


Now, my understanding of your question is the following: 


  given a finite deterministic automaton $\mathcal{A}= (Q, A, \cdot)$, decide whether
  the language accepted by $\mathcal{A}$ is a commutative language.


There is a polynomial algorithm to answer this question. 
Indeed a language is commutative if and only if its syntactic monoid is commutative. But the syntactic monoid $M(L)$ of $L$ is equal to the transition monoid of its minimal automaton. It follows that, $L$ is commutative if and only if the generators of $M(L)$ commute. In terms of automata, this is equivalent to check, for every pair of letters $(a, b)$, whether $q \cdot ab = q \cdot ba$ for all $q \in Q$. 

Now, given $\mathcal{A}$, you can compute the minimal automaton of $L$ in $O(|Q|\log |Q|)$ and then check commutativity in $O(|Q||A|^2)$.