# Example where equivalence is easy but finding class representative is hard

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 (*)).

• 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. Sep 26, 2018 at 18:09
• @Gamow In your example you could just let $f(s)=s$. I think the OP wants an example where no easy $f$ exists. Sep 26, 2018 at 18:26
• The keywords for search are "canonization" or "canonical labelling". Sep 26, 2018 at 19:13
• For those confused like me, apparently this question was reposted in 2018, and this was later noticed and the answers merged back here.
– usul
Oct 17, 2018 at 15:48

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).

• 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? Mar 14, 2012 at 1:04
• @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. Mar 14, 2012 at 1:11
• @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. :-) Mar 14, 2012 at 1:16
• Yes, sorry, that is what I meant. Mar 14, 2012 at 2:09

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. SIAM J. Comput. 13(4):682-689, 1984.

[2] Fortnow, L. and Grochow, J. A. Complexity classes of equivalence problems revisited. Inform. and Comput. 209(4):748-763, 2011. Also available on the arxiv.

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

If it does, then take any cryptographically strong hash 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.

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. Inform. and Comput. 209:4 (2011), 748-763. Also available as arXiv:0907.4775v2.

[2] Andreas Blass and Yuri Gurevich. Equivalence relations, invariants, and normal forms. SIAM J. Comput. 13:4 (1984), 24-42.

• 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 :) Oct 17, 2018 at 7:45

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.

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.)

• 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)$? Sep 27, 2018 at 6:05
• @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
Sep 27, 2018 at 7:33
• While the word "representative" might imply that the codomain of $f$ should be its domain, lifting this restriction makes this a non-example.
– jix
Sep 28, 2018 at 8:23
• (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. Sep 29, 2018 at 23:00

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. Note that a derandomized version of Babai’s algorithm would mean that no such example exist for graphs.

• Also of interest: For worst-case instead of average-case canonical forms, the recent paper by Schweitzer-Wiebking (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. Sep 29, 2018 at 23:17
• @JoshuaGrochow I didn’t hear about this, but that’s very exciting. Saving to read later. Sep 30, 2018 at 21:25

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.

• 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. Mar 14, 2012 at 0:09
• 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. Mar 14, 2012 at 1:43

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, which requires the Axiom of Choice and cannot be measurable.

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.

• Ah but in this case there is an easy choice of representative: just take $i$ to be anything and $b$ to be $\Phi(i)$. Oct 16, 2018 at 18:44

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.

• But in the case you describe, there is a different $f$ that is easy to compute: the identity function. Mar 13, 2012 at 21:49
• From the question, it's not clear whether the hardness is required from all $f$, rather than some $f$. Mar 13, 2012 at 22:15
• @MCH I think it's perfectly clear, since otherwise there would be no doubt at all and the question would be silly. Mar 14, 2012 at 13:19