Example where equivalence is easy but finding class representative is hard

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 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 6

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

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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.