25
$\begingroup$

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

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

11 Answers 11

25
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ruakh Mar 14 '12 at 1:04
  • 2
    $\begingroup$ @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. $\endgroup$ – Aaron Roth Mar 14 '12 at 1:11
  • $\begingroup$ @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. :-) $\endgroup$ – ruakh Mar 14 '12 at 1:16
  • $\begingroup$ Yes, sorry, that is what I meant. $\endgroup$ – David Eppstein Mar 14 '12 at 2:09
21
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – Bjørn Kjos-Hanssen Oct 17 '18 at 7:45
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – Bjørn Kjos-Hanssen Sep 27 '18 at 6:05
  • $\begingroup$ @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. $\endgroup$ – usul Sep 27 '18 at 7:33
  • $\begingroup$ While the word "representative" might imply that the codomain of $f$ should be its domain, lifting this restriction makes this a non-example. $\endgroup$ – jix Sep 28 '18 at 8:23
  • 1
    $\begingroup$ (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. $\endgroup$ – Joshua Grochow Sep 29 '18 at 23:00
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Sep 29 '18 at 23:17
  • $\begingroup$ @JoshuaGrochow I didn’t hear about this, but that’s very exciting. Saving to read later. $\endgroup$ – Stella Biderman Sep 30 '18 at 21:25
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Eppstein Mar 14 '12 at 0:09
  • $\begingroup$ 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. $\endgroup$ – David Harris Mar 14 '12 at 1:43
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Ah but in this case there is an easy choice of representative: just take $i$ to be anything and $b$ to be $\Phi(i)$. $\endgroup$ – Bjørn Kjos-Hanssen Oct 16 '18 at 18:44
-3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.