For different kinds of reversible finite automata, the complexity of decision problems, such as emptiness, universality, equivalence and inclusion, is investigated. For permutation automata, all these problems are L-complete. For permutation automata with multiple initial states, emptiness is L-complete and the rest are co-NP-complete. For sweeping permutation automata, all are co-NP-complete. For reversible automata, the results are similar to deterministic automata, but universality is easier: L-complete for one initial state (cf. NL-complete for DFA), co-NP-complete for multiple initial states (cf. PSPACE-complete for multiple-entry DFA) and co-NP-complete in the sweeping case (cf. PSPACE-complete for two-way DFA). The complexity of all the same problems is also determined in the case of a unary alphabet, where some problems become easier. Some partial results on testing minimality of these automata are obtained. Finally, length-bounded emptiness problems for several cases of permutation automata are proved to be PSPACE-complete, which is harder than the emptiness problem without the length bound.