Minimizing deterministic finite automata (DFAs) is a problem that has been thoroughly studied in the literature, and several algorithms have been proposed to solve the following problem: Given a DFA $\mathscr{A}$, compute a corresponding minimal DFA accepting the same language as $\mathscr{A}$.Most of these algorithms run in polynomial time.However, I wonder whether the decision variant of this problem - given a DFA $\mathscr{A}$, is $\mathscr{A}$ minimal? - can be solved more efficiently than actually computing the minimal automaton.Obviously, this can also be done efficiently by running for example Hopcroft's partition-refinement algorithm and then deciding whether all partitions contain precisely one state.As Yuval Filmus suggests in his answer, the decidability variant can be solved faster, possibly by using the standard algorithms.Unfortunately, I cannot see how (I hope I am not missing an obvious point here).Yuval points out in the comments here that the best known algorithms (like the one above) run in time $\mathcal{O}(n \log n)$ for constant-sized alphabets. Therefore, I am not only interested in asymptotically significant gains in runtime, as these seem rather unlikely. What bothers me most is that I cannot imagine any shortcut that might be drawn from the fact that we are only interested in a yes-no-answer - not even a shortcut that allows for saving an asymptotically negligible amount of time. I feel that every sensible algorithm that decides the minimality of a DFA would have to actually minimize the DFA and see if anything changes during the process. 
How fast can we decide whether a given DFA is minimal?
algorithms;formal languages;finite automata