Complexity classes of equivalence problems revisited (Q716333)

Equivalence relations on words over a finite alphabet give rise to a number of natural computational problems; in particular, the recognition problem (decide equivalence), the invariant problem (find a function whose kernel relation is the given equivalence relation), the canonical form problem (find a function that selects an element in each equivalence class) and the first canonical form problem (determine the least element in each class according to some natural order such as length-lex). The current work extends the results of \textit{A. Blass} and \textit{Yu. Gurevich} [SIAM J. Comput. 13, 682--689 (1984; Zbl 0545.68035)] and introduces connections to probabilistic and quantum computation. Among other results, it is shown in particular that if every relation with a polynomial time solvable recognition problem already admits a polynomial time solution to the invariant problem, then UP is contained in BQP. Various oracles are constructed that demonstrate potential separation between the different problems. For example, there is an oracle for which not every polynomial time decidable recognition problem admits a polynomial time invariant, nor does the invariant admits a polynomial time solution to the canonical form problem.