Summary: For an equivalence relation E on the words in some finite alphabet, we consider the recognition problem (decide whether two words are equivalent), the invariant problem (calculate a function constant on precisely the equivalence classes), the normal form problem (calculate a particular member of an equivalence class, given an arbitrary member) and the first member problem (calculate the first member of an equivalence class, given an arbitrary member). A solution for any of these problems yields solutions for earlier ones in the list. We show that, for polynomial time recognizable E, the first member problem is always in the class \(\Delta^ P_ 2\) (solvable in polynomial time with an oracle for an NP set) and can be complete for this class even when the normal problem is solvable in polynomial time. To distinguish between the other problems in the list, we construct an E whose invariant problem is not solvable in polynomial time with an oracle for E (although the first member problem is in \(NP^ E\cap co-NP^ E,\) and we construct an E whose normal form problem is not solvable in polynomial time with an oracle for a certain solution of its invariant problem.