Complexity Classes of Equivalence Problems Revisited

Lance Fortnow, Joshua A. Grochow

To determine if two lists of numbers are the same set, we sort both lists and see if we get the same result. The sorted list is a canonical form for the equivalence relation of set…