<p>Two integers $x,y$ mod $n$ are equivalent if $x^{2} \equiv y^{2}$ mod $n$. If one could easily compute a class representative for this function, then factoring can be done in probabilistic polynomial time.</p>

<p>In general, such an example would imply that $P \neq NP$. Suppose $R$ is an equivalence relation that is decidable in polynomial time. Then by lexicographic search using an $NP$ oracle, one can find the lexicographically least element in the equivalence class of any string. If $P=NP$, this becomes polynomial time, so you can use the lexicographically least equivalent string as a class representative. This observation is originally due to Blass and Gurevich [1].</p>

<p>Such an example would also imply $UP \not\subseteq BQP$ (and hence, in particluar, $P \neq UP$).</p>

<p>The question you've asked is exactly what we denoted $PEq =? Ker(FP)$ in our paper with Lance Fortnow [2]. That paper also includes the results I've stated here, as well as the example of hash functions pointed out by Peter Shor, a few other possible examples, and related results and questions.</p>

<p>[1] Blass, A. and Gurevich, Y. <a href="http://dx.doi.org/10.1137/0213042">Equivalence relations, invariants, and normal forms</a>.  SIAM J. Comput. 13(4):682-689, 1984.</p>

<p>[2] Fortnow, L. and Grochow, J. A. <a href="http://dx.doi.org/10.1016/j.ic.2011.01.006">Complexity classes of equivalence problems revisited</a>. Inform. and Comput. 209(4):748-763, 2011. Also available on the <a href="http://arxiv.org/abs/0907.4775">arxiv</a>.</p>

CC BY-SA 3.0
2012-03-13T23:06:55.993Z
2012-03-14T03:24:52.683Z
2012-03-14T03:24:52.683Z
Joshua Grochow
<p>Ok, how about: numbers $x$ and $y$ are equivalent if either $x=y$, or both $x$ and $y$ have factorizations $x=pq$ and $y=pr$ where $p$, $q$, and $r$ are all prime and $p &lt; \min(q,r)$. That is: products of two primes are equivalent when they share their smallest prime factor; other numbers are only equivalent to themselves.</p>

<p>It's easy to test whether two different numbers are equivalent: compute their gcd, test whether it's nontrivial, test whether the gcd is less than the cofactors, and test whether the gcd and its cofactors are all prime.</p>

<p>But it's not obvious how to compute a representative function $f$ in polynomial time, and if you add the requirement that $f(x)$ must be equivalent to $x$ then any representative function would allow us to factor most products of two primes (every one that isn't its own representative).</p>

CC BY-SA 3.0
2012-03-14T01:04:27.743Z
Re: "it's not obvious how to compute a representative function *f*": Probably I'm misunderstanding you, but: if *x* is the product of two distinct primes, then: let *p* be the lesser of these primes; let *s* be the least prime after *p*; choose *f* (*x*) = *ps*. If *x* is *not* the product of two distinct primes, then choose *f* (*x*) = *x*. (All of which is a roundabout way of saying: choose *f* (*x*) = the least element of *x*'s equivalence class.) No?
ruakh
CC BY-SA 3.0
2012-03-14T01:11:17.060Z
@ruakh "Let $p$ be the lesser of these primes" presumes you can factor $x$ (to find $p$), but this is commonly assumed to be hard.
Aaron Roth
CC BY-SA 3.0
2012-03-14T01:16:09.443Z
@AaronRoth: Ah, I see. By "it's not obvious how to compute a representative function $f$", he must have meant something like "it's not obvious how to *easily* compute a representative function $f$", then. Which fits with the OP's question. That makes sense, thank you. :-)
ruakh
CC BY-SA 3.0
2012-03-14T02:09:47.003Z
Yes, sorry, that is what I meant.
David Eppstein
CC BY-SA 3.0
2012-03-13T22:08:52.650Z
2012-03-15T15:47:39.043Z
2012-03-15T15:47:39.043Z
David Eppstein
<p>Does the "representative" have to be in the equivalence class?</p>

<p>If it does, then take any <a href="http://en.wikipedia.org/wiki/Cryptographic_hash_function">cryptographically strong hash</a> function $f$ with collision resistance.</p>

<p>Let $x \simeq y$ if $f(x) = f(y)\,$. It's easy to test whether two things are equivalent, but if, given $f(x) = h$, you could find a canonical preimage of $h$, then you could find two strings $x$ and $y$ such that $f(x)=f(y)\,$. This is supposed to be hard (that's what collision resistance means). </p>

<p>Of course, computer scientists cannot prove that cryptographically strong hash functions with collision resistance exist, but they have a number of candidates.</p>

CC BY-SA 3.0
2012-03-14T01:25:39.913Z
2012-03-14T01:33:43.430Z
2012-03-14T01:33:43.430Z
Peter Shor 
<p>First, what you are really asking for is typically called a complete invariant. A canonical or normal form also requires that <span class="math-container">$f(x)$</span> is equivalent to <span class="math-container">$x$</span> for all <span class="math-container">$x$</span>. (Asking for a "representative" is a bit ambiguous, as some authors might mean this to include the condition of canonical form.) </p>

<p>Second, please forgive the shameless self-promotion, but this is exactly one of the questions Fortnow and I worked on [1]. We showed that if every equivalence relation that can be decided in <span class="math-container">$\mathsf{P}$</span> also has a complete invariant in <span class="math-container">$\mathsf{FP}$</span>, then bad things happen. In particular, it would imply <span class="math-container">$\mathsf{UP} \subseteq \mathsf{BQP}$</span>. If a promise version of this statement holds (see Theorem 4.6) then <span class="math-container">$\mathsf{NP} \subseteq \mathsf{BQP} \cap \mathsf{SZK}$</span> and <span class="math-container">$\mathsf{PH} = \mathsf{AM}$</span>.</p>

<p>Now, if you actually want a canonical form (a representative of each equivalence class that's also in the equivalence class), we show even worse things happen. That is, if every equivalence relation decidable in polynomial-time has a poly-time canonical form, then:</p>

<ul>
<li>Integers can be factored in probabilistic poly time</li>
<li>Collision-free hash functions that can be evaluated in <span class="math-container">$\mathsf{FP}$</span> do not exist.</li>
<li><span class="math-container">$\mathsf{NP} = \mathsf{UP} = \mathsf{RP}$</span> (hence <span class="math-container">$\mathsf{PH} = \mathsf{BPP}$</span>)</li>
</ul>

<p>There are also oracles going both ways for most of these statements about equivalence relations, due to us and to Blass and Gurevich [2].</p>

<p>If instead of "any" representative, you ask for the lexicographically least element in an equivalence class, finding the lexicographically smallest element in an equivalence class can be <span class="math-container">$NP$</span>-hard (in fact, <span class="math-container">$P^{NP}$</span>-hard) - even if the relationship has a polynomial-time canonical form [2].</p>

<p>[1] Lance Fortnow and Joshua A. Grochow. <a href="http://dx.doi.org/10.1016/j.ic.2011.01.006" rel="noreferrer">Complexity classes of equivalence problems revisited</a>. Inform. and Comput. 209:4 (2011), 748-763. Also available as <a href="http://arxiv.org/abs/0907.4775v2" rel="noreferrer">arXiv:0907.4775v2</a>.</p>

<p>[2] Andreas Blass and Yuri Gurevich. <a href="http://dx.doi.org/10.1137/0213042" rel="noreferrer">Equivalence relations, invariants, and normal forms</a>. SIAM J. Comput. 13:4 (1984), 24-42.</p>

CC BY-SA 4.0
2018-10-17T07:45:06.383Z
It turned out that the version of this question posted in 2018 was a repost by a spam user of a question from 2012. Maybe merge your two answers? They both mention UP and BQP but in negated ways... you'd lose some rep but I'd partially mitigate that by upvoting your old answer :)
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-09-29T23:13:46.160Z
2018-09-29T23:13:46.160Z
Joshua Grochow
<p>Here's an attempt at another answer, where we loosen the requirement on the "representative"; it doesn't actually have to be a member of the equivalence class, but just a function identifying the equivalence class. </p>

<p>Suppose you have a group where you can do subgroup membership testing. That is, given $g_1, g_2, \ldots, g_k$, you can check whether $h$ is in the subgroup generated by $g_1, \ldots, g_k$. </p>

<p>Take your equivalence classes to be sets of elements $g_1, g_2, \ldots, g_k$ that generate the same subgroup. It's easy to check whether two sets generate the same subgroup. However, it's not at all  clear how you could find a unique identifier for every subgroup. I suspect that this really is an example if you assume black-box groups with subgroup membership testing. However, I don't know whether there is any non-oracle group where this problem appears to be hard. </p>

CC BY-SA 3.0
2012-03-16T10:58:23.763Z
2012-03-16T10:58:23.763Z
Peter Shor 
<p>Here's a contrived example. The objects are pairs <span class="math-container">$(H,X)$</span> where <span class="math-container">$H$</span> is a SAT formula and <span class="math-container">$X$</span> is a proposed assignment to the variables. Say <span class="math-container">$(H,X) \sim (H',X')$</span> if <span class="math-container">$H=H'$</span> and either (a) <span class="math-container">$X$</span> and <span class="math-container">$X'$</span> are both satisfying assignments, or (b) <span class="math-container">$X$</span> and <span class="math-container">$X'$</span> are both not satisfying assignments. This is reflexive, symmetric, and transitive. Each unsatisfiable <span class="math-container">$H$</span> has one equivalence class consisting of all <span class="math-container">$(H,X)$</span>. Each satisfiable <span class="math-container">$H$</span> has a class of all <span class="math-container">$(H,X)$</span> where <span class="math-container">$X$</span> is a satisfying assignment, and another class with the non-satisfying ones.</p>

<p>Checking whether <span class="math-container">$(H,X) \sim (H',X')$</span> is easy since we just check if <span class="math-container">$H=H'$</span>, then if <span class="math-container">$X$</span> satisfies <span class="math-container">$H$</span>, then if <span class="math-container">$X'$</span> satisfies <span class="math-container">$H$</span>. But to compute a canonical member of a class given <span class="math-container">$(H,X)$</span> with <span class="math-container">$H$</span> satisfied by <span class="math-container">$X$</span> seems too hard (I'm not sure how best to prove hardness). We can easily plant an extra solution to SAT instances, so knowing one solution won't generally help us find any other solution, let alone pick a canonical one. (Edit: What I mean is that I don't expect any efficient algorithm for finding additional solutions given a first solution. Because we could use it to solve SAT problems by first "planting" an extra solution into the problem, then feeding it to the algorithm. See comments.)</p>

CC BY-SA 4.0
2018-09-27T06:05:06.503Z
By "plant", do you mean something like: given a SAT instance $H=\bigwedge_i\varphi_i$ in CNF, let's add a new variable $p$ not occuring in $H$, and let
$K = \bigwedge_i (\varphi_i\vee p)$?
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-09-27T07:33:50.027Z
@BjørnKjos-Hanssen, yeah, something like that. Ideally we would create exactly one additional solution. So I think this works (not in CNF though): given a generic SAT formula $H$, let $K = (H \land \lnot p) \lor (p \land x_1 \cdots \land x_n)$ where $\{x_i\}$ are the original variables. So just to clarify, if we had an algorithm to check for/find a second solution to SAT instances, then given any $H$ we would construct $K$ and feed it to that algorithm along with the all-true assignment and it would solve the original instance. If I haven't missed anything.
usul
CC BY-SA 4.0
2018-09-28T08:23:22.337Z
While the word "representative" might imply that the codomain of $f$ should be its domain, lifting this restriction makes this a non-example.
jix
CC BY-SA 4.0
2018-09-29T23:00:03.703Z
(1) Finding a second satisfying assignment is still NP-hard. (2) Finding a canonical member of the class given (H,X) in polynomial-time is equivalent to $NPMV \subseteq_c NPSV$, which collapses PH (Hemaspaandra-Naik-Ogihara-Selman). However, note that the question doesn't actually ask for a canonical member of the class, since it doesn't require x to be equivalent to f(x), it is really only asking for a complete invariant.
Joshua Grochow
CC BY-SA 4.0
2018-09-27T05:25:22.870Z
2018-09-27T07:36:43.213Z
2018-09-27T07:36:43.213Z
usul
<p>This is an open question, at least for graphs. I believe that the latest progress is</p>

<blockquote>
  <p>Babai and Kucera, "Canonical labeling of graphs in linear average time," FOCS, 1979</p>
</blockquote>

<p>which gives an (expected) linear time algorithm for a canonical graph that is correct with probability $1 - \frac{1}{2^{O(n)}}$</p>

<p>You can read more <a href="https://en.m.wikipedia.org/wiki/Graph_canonization" rel="nofollow noreferrer">on Wikipedia</a>. Note that a derandomized version of Babai’s algorithm would mean that no such example exist for graphs.</p>

CC BY-SA 4.0
2018-09-29T23:17:08.267Z
Also of interest: For worst-case instead of average-case canonical forms, the recent paper by Schweitzer-Wiebking (https://arxiv.org/abs/1806.07466) gives a technique that gives good canonical forms for many related equivalence relations (code equivalence, permutation group conjugacy, hypergraph iso), and in their final section they suggest that their techniques might apply to Babai's result as well, giving a quasi-poly-time canonical form for GI.
Joshua Grochow
CC BY-SA 4.0
2018-09-30T21:25:37.630Z
@JoshuaGrochow I didn’t hear about this, but that’s very exciting. Saving to read later.
Stella Biderman
CC BY-SA 4.0
2018-09-26T20:58:20.367Z
2018-09-27T12:09:03.897Z
2018-09-27T12:09:03.897Z
Stella Biderman
<p>Testing whether two circuits of size $\leq N$ circuits are equivalent.</p>

<p>To determine if $C_1 \sim C_2$ you only need to evaluate at the $2^n$ input points. To determine a class representative, one would probably have to test all $2^{\Omega(N \log N)}$ possible circuits.  For $N$ sufficiently large this is exponentially harder than testing circuit equivalence.</p>

CC BY-SA 3.0
2012-03-14T00:09:51.193Z
Here's a function $f$ that maps each circuit to a representative object (not a circuit) as quickly as equivalence testing: map each circuit to the vector of $2^n$ outputs for each possible input. Probably it would be not difficult to turn this into an explicit crossbar-style circuit.
David Eppstein
CC BY-SA 3.0
2012-03-14T01:43:14.730Z
I insisted that the circuits had bounded size in order to prevent an easy mapping from $2^n$ outputs to circuit. However, I had assumed that the function $f$ needed to map to a class representative as opposed to an arbitrary string.
David Harris
CC BY-SA 3.0
2012-03-13T22:53:39.053Z
2012-03-13T22:53:39.053Z
David Harris
<p>A famous example from descriptive set theory:</p>

<p>Let us define an equivalence relation <span class="math-container">$\sim$</span> on <span class="math-container">$\mathbb R$</span> by
<span class="math-container">$$r\sim s\iff r-s\in\mathbb Q.$$</span></p>

<p>This is a rather "easy" equivalence relation, in particular it's measurable.</p>

<p>But finding representatives amounts to finding a <a href="https://en.wikipedia.org/wiki/Vitali_set" rel="nofollow noreferrer">Vitali set</a>, which requires the Axiom of Choice and cannot be measurable.</p>

CC BY-SA 4.0
2018-09-28T06:46:49.783Z
2018-09-28T06:51:50.303Z
2018-09-28T06:51:50.303Z
Bjørn Kjos-Hanssen
<p>Let the objects in your universe be the triples (<span class="math-container">$\Phi, b, i)$</span> where <span class="math-container">$\Phi$</span> be a Satisfiability problem, on variables <span class="math-container">$x_0, \ldots, x_{k-1}$</span>, <span class="math-container">$b$</span> is either 0 or 1, and <span class="math-container">$i$</span> is a bitstring of length <span class="math-container">$k$</span>, where <span class="math-container">$\Phi(i)=b$</span>.  That is, <span class="math-container">$i$</span> is an assignment to <span class="math-container">$x_0, \ldots, x_k$</span> that satisfies <span class="math-container">$\Phi$</span> if <span class="math-container">$b$</span> is 1 or does not satisfy <span class="math-container">$\Phi$</span> if <span class="math-container">$b$</span> is 0.  </p>

<p>Two objects are equivalent if they have the same <span class="math-container">$\Phi$</span>.  Easy to check.</p>

<p>Let the representative object be the lexicographically greatest among all in the equivalence class. </p>

<p>The representative is NP-complete to find: it would solve SAT, since if the lexicographically greatest has <span class="math-container">$b=0$</span>, then <span class="math-container">$\Phi$</span> is unsatisfiable; if it has <span class="math-container">$b=1$</span>, it is satisfiable.</p>

<p>Seems that most NP-complete problems can be posed this way; it's a matter of placing the certificate of membership into the encoding of the element.</p>

<p>I thought maybe this was a homework problem, which is why I didn't post the solution earlier.  I should have done; I could have used those points that @david-eppstien got.  Goodness knows, he doesn't need them.</p>

CC BY-SA 4.0
2018-10-16T18:44:58.427Z
Ah but in this case there is an easy choice of representative: just take $i$ to be anything and $b$ to be $\Phi(i)$.
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-10-16T18:26:00.383Z
2018-10-16T18:26:00.383Z
Gara Pruesse
<p>I suppose you can easily achieve that for virtually any problem of the type you describe.</p>

<p>Trivial example: Suppose objects are strings, and any $x$ is equivalent to only itself. Determining whether two elements are equivalent is always easy (it is simply equality). However, you can define $f()$ as your favorite injective hard function.</p>

CC BY-SA 3.0
2012-03-13T21:49:59.100Z
But in the case you describe, there is a different $f$ that is easy to compute: the identity function.
David Eppstein
CC BY-SA 3.0
2012-03-13T22:15:30.333Z
From the question, it's not clear whether the hardness is required from all $f$, rather than some $f$.
Mahdi Cheraghchi
CC BY-SA 3.0
2012-03-14T13:19:36.477Z
@MCH I think it's perfectly clear, since otherwise there would be no doubt at all and the question would be silly.
Random832
CC BY-SA 3.0
2012-03-13T21:11:43.003Z
2012-03-13T21:11:43.003Z
Mahdi Cheraghchi
<p>Suppose we have a class of objects (say graphs, strings), and an equivalence relation on these objects. For graphs this could be graph isomorphism. For strings, we could declare two strings equivalent if they are anagrams of each other.</p>

<p>I am interested in computing a representative for an equivalence class. That is, I want a function f() such that for any two objects x, y,
f(x) = f(y) iff x and y are equivalent.  (*)</p>

<p>For the example of anagrams, f(s) could sort letters in the string, ie. f('cabac') = 'aabcc'. For graph isomorphism, we could take f(G) to be a graph G' that is isomorphic to G and is the lexicoraphically first graph to have this property.</p>

<p>Now the question: Is there an example where the problem of determining whether two elements are equivalent is "easy" (poly time solvable), while finding a representative is difficult (i.e. there is no poly time algorithm to compute f() that satisfies (*)).</p>

CC BY-SA 4.0
2018-09-26T18:09:17.377Z
The question might be too general, as it allows lots of "weird" constructions: Take an NP-complete problem, and let every instance form its own equivalence class. For a NO-instance $s$, set $f(s)=0$. For a YES-instance $s$, define $s$ as the lexicographically smallest certificate.
Gamow
CC BY-SA 4.0
2018-09-26T18:26:22.173Z
@Gamow In your example you could just let $f(s)=s$. I think the OP wants an example where no easy $f$ exists.
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-09-26T19:13:45.970Z
The keywords for search are "canonization" or "canonical labelling".
Emil Jeřábek
CC BY-SA 4.0
2018-10-17T15:48:29.087Z
For those confused like me, apparently this question was reposted in 2018, and this was later noticed and the answers merged back here.
usul
<cc.complexity-theory>
Example where equivalence is easy but finding class representative is hard
Martin Pál
# Example where equivalence is easy but finding class representative is hard

(Asked by: username_0 on 2012-03-13)

Suppose we have a class of objects (say graphs, strings), and an equivalence relation on these objects. For graphs this could be graph isomorphism. For strings, we could declare two strings equivalent if they are anagrams of each other.

I am interested in computing a representative for an equivalence class. That is, I want a function f() such that for any two objects x, y,
f(x) = f(y) iff x and y are equivalent. (\*)

For the example of anagrams, f(s) could sort letters in the string, ie. f('cabac') = 'aabcc'. For graph isomorphism, we could take f(G) to be a graph G' that is isomorphic to G and is the lexicoraphically first graph to have this property.

Now the question: Is there an example where the problem of determining whether two elements are equivalent is "easy" (poly time solvable), while finding a representative is difficult (i.e. there is no poly time algorithm to compute f() that satisfies (\*)).

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: The question might be too general, as it allows lots of "weird" constructions: Take an NP-complete problem, and let every instance form its own equivalence class. For a NO-instance $s$, set $f(s)=0$. For a YES-instance $s$, define $s$ as the lexicographically smallest certificate.  
> **username_2**: @Gamow In your example you could just let $f(s)=s$. I think the OP wants an example where no easy $f$ exists.  
> **username_3**: The keywords for search are "canonization" or "canonical labelling".  
> **username_4**: For those confused like me, apparently this question was reposted in 2018, and this was later noticed and the answers merged back here.  

---

## 11 answers

### Answer by username_6 on 2012-03-13. Score: 26

Ok, how about: numbers $x$ and $y$ are equivalent if either $x=y$, or both $x$ and $y$ have factorizations $x=pq$ and $y=pr$ where $p$, $q$, and $r$ are all prime and $p < \min(q,r)$. That is: products of two primes are equivalent when they share their smallest prime factor; other numbers are only equivalent to themselves.

It's easy to test whether two different numbers are equivalent: compute their gcd, test whether it's nontrivial, test whether the gcd is less than the cofactors, and test whether the gcd and its cofactors are all prime.

But it's not obvious how to compute a representative function $f$ in polynomial time, and if you add the requirement that $f(x)$ must be equivalent to $x$ then any representative function would allow us to factor most products of two primes (every one that isn't its own representative).

> **Comments:**
> **username_7**: Re: "it's not obvious how to compute a representative function *f*": Probably I'm misunderstanding you, but: if *x* is the product of two distinct primes, then: let *p* be the lesser of these primes; let *s* be the least prime after *p*; choose *f* (*x*) = *ps*. If *x* is *not* the product of two distinct primes, then choose *f* (*x*) = *x*. (All of which is a roundabout way of saying: choose *f* (*x*) = the least element of *x*'s equivalence class.) No?  
> **username_8**: @ruakh "Let $p$ be the lesser of these primes" presumes you can factor $x$ (to find $p$), but this is commonly assumed to be hard.  
> **username_7**: @AaronRoth: Ah, I see. By "it's not obvious how to compute a representative function $f$", he must have meant something like "it's not obvious how to *easily* compute a representative function $f$", then. Which fits with the OP's question. That makes sense, thank you. :-)  
> **username_6**: Yes, sorry, that is what I meant.  

---

### Answer by username_5 on 2012-03-13. Score: 22

Two integers $x,y$ mod $n$ are equivalent if $x^{2} \equiv y^{2}$ mod $n$. If one could easily compute a class representative for this function, then factoring can be done in probabilistic polynomial time.

In general, such an example would imply that $P \neq NP$. Suppose $R$ is an equivalence relation that is decidable in polynomial time. Then by lexicographic search using an $NP$ oracle, one can find the lexicographically least element in the equivalence class of any string. If $P=NP$, this becomes polynomial time, so you can use the lexicographically least equivalent string as a class representative. This observation is originally due to Blass and Gurevich [1].

Such an example would also imply $UP \not\subseteq BQP$ (and hence, in particluar, $P \neq UP$).

The question you've asked is exactly what we denoted $PEq =? Ker(FP)$ in our paper with Lance Fortnow [2]. That paper also includes the results I've stated here, as well as the example of hash functions pointed out by Peter Shor, a few other possible examples, and related results and questions.

[1] Blass, A. and Gurevich, Y. [Equivalence relations, invariants, and normal forms](http://dx.doi.org/10.1137/0213042). SIAM J. Comput. 13(4):682-689, 1984.

[2] Fortnow, L. and Grochow, J. A. [Complexity classes of equivalence problems revisited](http://dx.doi.org/10.1016/j.ic.2011.01.006). Inform. and Comput. 209(4):748-763, 2011. Also available on the [arxiv](http://arxiv.org/abs/0907.4775).


---

### Answer by username_9 on 2012-03-14. Score: 15

Does the "representative" have to be in the equivalence class?

If it does, then take any [cryptographically strong hash](http://en.wikipedia.org/wiki/Cryptographic_hash_function) function $f$ with collision resistance.

Let $x \simeq y$ if $f(x) = f(y)\,$. It's easy to test whether two things are equivalent, but if, given $f(x) = h$, you could find a canonical preimage of $h$, then you could find two strings $x$ and $y$ such that $f(x)=f(y)\,$. This is supposed to be hard (that's what collision resistance means).

Of course, computer scientists cannot prove that cryptographically strong hash functions with collision resistance exist, but they have a number of candidates.


---

### Answer by username_5 on 2018-09-29. Score: 7

First, what you are really asking for is typically called a complete invariant. A canonical or normal form also requires that $f(x)$ is equivalent to $x$ for all $x$. (Asking for a "representative" is a bit ambiguous, as some authors might mean this to include the condition of canonical form.)

Second, please forgive the shameless self-promotion, but this is exactly one of the questions Fortnow and I worked on [1]. We showed that if every equivalence relation that can be decided in $\mathsf{P}$ also has a complete invariant in $\mathsf{FP}$, then bad things happen. In particular, it would imply $\mathsf{UP} \subseteq \mathsf{BQP}$. If a promise version of this statement holds (see Theorem 4.6) then $\mathsf{NP} \subseteq \mathsf{BQP} \cap \mathsf{SZK}$ and $\mathsf{PH} = \mathsf{AM}$.

Now, if you actually want a canonical form (a representative of each equivalence class that's also in the equivalence class), we show even worse things happen. That is, if every equivalence relation decidable in polynomial-time has a poly-time canonical form, then:

* Integers can be factored in probabilistic poly time
* Collision-free hash functions that can be evaluated in $\mathsf{FP}$ do not exist.
* $\mathsf{NP} = \mathsf{UP} = \mathsf{RP}$ (hence $\mathsf{PH} = \mathsf{BPP}$)

There are also oracles going both ways for most of these statements about equivalence relations, due to us and to Blass and Gurevich [2].

If instead of "any" representative, you ask for the lexicographically least element in an equivalence class, finding the lexicographically smallest element in an equivalence class can be $NP$-hard (in fact, $P^{NP}$-hard) - even if the relationship has a polynomial-time canonical form [2].

[1] Lance Fortnow and Joshua A. Grochow. [Complexity classes of equivalence problems revisited](http://dx.doi.org/10.1016/j.ic.2011.01.006). Inform. and Comput. 209:4 (2011), 748-763. Also available as [arXiv:0907.4775v2](http://arxiv.org/abs/0907.4775v2).

[2] Andreas Blass and Yuri Gurevich. [Equivalence relations, invariants, and normal forms](http://dx.doi.org/10.1137/0213042). SIAM J. Comput. 13:4 (1984), 24-42.

> **Comments:**
> **username_2**: It turned out that the version of this question posted in 2018 was a repost by a spam user of a question from 2012. Maybe merge your two answers? They both mention UP and BQP but in negated ways... you'd lose some rep but I'd partially mitigate that by upvoting your old answer :)  

---

### Answer by username_9 on 2012-03-16. Score: 5

Here's an attempt at another answer, where we loosen the requirement on the "representative"; it doesn't actually have to be a member of the equivalence class, but just a function identifying the equivalence class.

Suppose you have a group where you can do subgroup membership testing. That is, given $g\_1, g\_2, \ldots, g\_k$, you can check whether $h$ is in the subgroup generated by $g\_1, \ldots, g\_k$.

Take your equivalence classes to be sets of elements $g\_1, g\_2, \ldots, g\_k$ that generate the same subgroup. It's easy to check whether two sets generate the same subgroup. However, it's not at all clear how you could find a unique identifier for every subgroup. I suspect that this really is an example if you assume black-box groups with subgroup membership testing. However, I don't know whether there is any non-oracle group where this problem appears to be hard.


---

### Answer by username_4 on 2018-09-27. Score: 4

Here's a contrived example. The objects are pairs $(H,X)$ where $H$ is a SAT formula and $X$ is a proposed assignment to the variables. Say $(H,X) \sim (H',X')$ if $H=H'$ and either (a) $X$ and $X'$ are both satisfying assignments, or (b) $X$ and $X'$ are both not satisfying assignments. This is reflexive, symmetric, and transitive. Each unsatisfiable $H$ has one equivalence class consisting of all $(H,X)$. Each satisfiable $H$ has a class of all $(H,X)$ where $X$ is a satisfying assignment, and another class with the non-satisfying ones.

Checking whether $(H,X) \sim (H',X')$ is easy since we just check if $H=H'$, then if $X$ satisfies $H$, then if $X'$ satisfies $H$. But to compute a canonical member of a class given $(H,X)$ with $H$ satisfied by $X$ seems too hard (I'm not sure how best to prove hardness). We can easily plant an extra solution to SAT instances, so knowing one solution won't generally help us find any other solution, let alone pick a canonical one. (Edit: What I mean is that I don't expect any efficient algorithm for finding additional solutions given a first solution. Because we could use it to solve SAT problems by first "planting" an extra solution into the problem, then feeding it to the algorithm. See comments.)

> **Comments:**
> **username_2**: By "plant", do you mean something like: given a SAT instance $H=\bigwedge_i\varphi_i$ in CNF, let's add a new variable $p$ not occuring in $H$, and let $K = \bigwedge_i (\varphi_i\vee p)$?  
> **username_4**: @BjørnKjos-Hanssen, yeah, something like that. Ideally we would create exactly one additional solution. So I think this works (not in CNF though): given a generic SAT formula $H$, let $K = (H \land \lnot p) \lor (p \land x_1 \cdots \land x_n)$ where $\{x_i\}$ are the original variables. So just to clarify, if we had an algorithm to check for/find a second solution to SAT instances, then given any $H$ we would construct $K$ and feed it to that algorithm along with the all-true assignment and it would solve the original instance. If I haven't missed anything.  
> **username_10**: While the word "representative" might imply that the codomain of $f$ should be its domain, lifting this restriction makes this a non-example.  
> **username_5**: (1) Finding a second satisfying assignment is still NP-hard. (2) Finding a canonical member of the class given (H,X) in polynomial-time is equivalent to $NPMV \subseteq_c NPSV$, which collapses PH (Hemaspaandra-Naik-Ogihara-Selman). However, note that the question doesn't actually ask for a canonical member of the class, since it doesn't require x to be equivalent to f(x), it is really only asking for a complete invariant.  

---

### Answer by username_11 on 2018-09-26. Score: 4

This is an open question, at least for graphs. I believe that the latest progress is

> Babai and Kucera, "Canonical labeling of graphs in linear average time," FOCS, 1979

which gives an (expected) linear time algorithm for a canonical graph that is correct with probability $1 - \frac{1}{2^{O(n)}}$

You can read more [on Wikipedia](https://en.m.wikipedia.org/wiki/Graph_canonization). Note that a derandomized version of Babai’s algorithm would mean that no such example exist for graphs.

> **Comments:**
> **username_5**: Also of interest: For worst-case instead of average-case canonical forms, the recent paper by Schweitzer-Wiebking (https://arxiv.org/abs/1806.07466) gives a technique that gives good canonical forms for many related equivalence relations (code equivalence, permutation group conjugacy, hypergraph iso), and in their final section they suggest that their techniques might apply to Babai's result as well, giving a quasi-poly-time canonical form for GI.  
> **username_11**: @JoshuaGrochow I didn’t hear about this, but that’s very exciting. Saving to read later.  

---

### Answer by username_12 on 2012-03-13. Score: 2

Testing whether two circuits of size $\leq N$ circuits are equivalent.

To determine if $C\_1 \sim C\_2$ you only need to evaluate at the $2^n$ input points. To determine a class representative, one would probably have to test all $2^{\Omega(N \log N)}$ possible circuits. For $N$ sufficiently large this is exponentially harder than testing circuit equivalence.

> **Comments:**
> **username_6**: Here's a function $f$ that maps each circuit to a representative object (not a circuit) as quickly as equivalence testing: map each circuit to the vector of $2^n$ outputs for each possible input. Probably it would be not difficult to turn this into an explicit crossbar-style circuit.  
> **username_12**: I insisted that the circuits had bounded size in order to prevent an easy mapping from $2^n$ outputs to circuit. However, I had assumed that the function $f$ needed to map to a class representative as opposed to an arbitrary string.  

---

### Answer by username_2 on 2018-09-28. Score: 1

A famous example from descriptive set theory:

Let us define an equivalence relation $\sim$ on $\mathbb R$ by
$$r\sim s\iff r-s\in\mathbb Q.$$

This is a rather "easy" equivalence relation, in particular it's measurable.

But finding representatives amounts to finding a [Vitali set](https://en.wikipedia.org/wiki/Vitali_set), which requires the Axiom of Choice and cannot be measurable.


---

### Answer by username_13 on 2018-10-16. Score: 0

Let the objects in your universe be the triples ($\Phi, b, i)$ where $\Phi$ be a Satisfiability problem, on variables $x\_0, \ldots, x\_{k-1}$, $b$ is either 0 or 1, and $i$ is a bitstring of length $k$, where $\Phi(i)=b$. That is, $i$ is an assignment to $x\_0, \ldots, x\_k$ that satisfies $\Phi$ if $b$ is 1 or does not satisfy $\Phi$ if $b$ is 0.

Two objects are equivalent if they have the same $\Phi$. Easy to check.

Let the representative object be the lexicographically greatest among all in the equivalence class.

The representative is NP-complete to find: it would solve SAT, since if the lexicographically greatest has $b=0$, then $\Phi$ is unsatisfiable; if it has $b=1$, it is satisfiable.

Seems that most NP-complete problems can be posed this way; it's a matter of placing the certificate of membership into the encoding of the element.

I thought maybe this was a homework problem, which is why I didn't post the solution earlier. I should have done; I could have used those points that @david-eppstien got. Goodness knows, he doesn't need them.

> **Comments:**
> **username_2**: Ah but in this case there is an easy choice of representative: just take $i$ to be anything and $b$ to be $\Phi(i)$.  

---

### Answer by username_14 on 2012-03-13. Score: -3

I suppose you can easily achieve that for virtually any problem of the type you describe.

Trivial example: Suppose objects are strings, and any $x$ is equivalent to only itself. Determining whether two elements are equivalent is always easy (it is simply equality). However, you can define $f()$ as your favorite injective hard function.

> **Comments:**
> **username_6**: But in the case you describe, there is a different $f$ that is easy to compute: the identity function.  
> **username_14**: From the question, it's not clear whether the hardness is required from all $f$, rather than some $f$.  
> **username_15**: @MCH I think it's perfectly clear, since otherwise there would be no doubt at all and the question would be silly.  

---

