Exemple où l'équivalence est facile mais où trouver un représentant de classe est difficile

Supposons que nous ayons une classe d'objets (par exemple des graphiques, des chaînes) et une relation d'équivalence sur ces objets. Pour les graphiques, cela pourrait être un isomorphisme de graphique. Pour les chaînes, nous pourrions déclarer deux chaînes équivalentes si elles sont des anagrammes l'une de l'autre.

Je souhaite calculer un représentant pour une classe d'équivalence. Autrement dit, je veux une fonction f () telle que pour deux objets quelconques x, y, f (x) = f (y) ssi x et y sont équivalents. (*)

Pour l'exemple d'anagrammes, f (s) pourrait trier les lettres dans la chaîne, c'est-à-dire. f ('cabac') = 'aabcc'. Pour l'isomorphisme de graphe, nous pourrions prendre f (G) pour être un graphe G 'qui est isomorphe à G et est le premier graphe lexicoraphiquement à avoir cette propriété.

Maintenant, la question est: y a-t-il un exemple où le problème de déterminer si deux éléments sont équivalents est "facile" (poly temps résoluble), alors que trouver un représentant est difficile (c'est-à-dire qu'il n'y a pas d'algorithme poly temps pour calculer f () qui satisfait ( *)).

$x$$y$$x=y$$x$$y$$x=pq$$y=pr$$p$$q$$r$$p < \min(q,r)$

Il est facile de tester si deux nombres différents sont équivalents: calculer leur pgcd, tester s'il n'est pas trivial, tester si le pgcd est inférieur aux cofacteurs et tester si le pgcd et ses cofacteurs sont tous premiers.

Mais il n'est pas évident de calculer une fonction représentative en temps polynomial, et si vous ajoutez l'exigence que doit être équivalent à alors n'importe quelle fonction représentative nous permettrait de factoriser la plupart des produits de deux nombres premiers (chacun qui n'est pas 't son propre représentant).$f$$f(x)$$x$

Deux entiers mod n sont équivalents si x 2 ≡ y 2 mod n . Si l'on pouvait facilement calculer un représentant de classe pour cette fonction, alors l'affacturage peut se faire en temps polynomial probabiliste.$x,y$$n$$x^{2} \equiv y^{2}$$n$

En général, un tel exemple impliquerait que . Supposons que R est une relation d'équivalence décidable en temps polynomial. Ensuite, par recherche lexicographique en utilisant un oracle N P , on peut trouver l'élément lexicographiquement le moins dans la classe d'équivalence de n'importe quelle chaîne. Si P = N P , cela devient le temps polynomial, vous pouvez donc utiliser la chaîne lexicographiquement la moins équivalente comme représentant de classe. Cette observation est à l'origine due à Blass et Gurevich [1].$P \neq NP$$R$$NP$$P=NP$

Un tel exemple impliquerait également (et donc, en particulier, ).$UP \not\subseteq BQP$$P \neq UP$

La question que vous avez posée est exactement ce que nous avons noté dans notre article avec Lance Fortnow [2]. Ce document comprend également les résultats que j'ai énoncés ici, ainsi que l'exemple des fonctions de hachage souligné par Peter Shor, quelques autres exemples possibles, et les résultats et questions connexes.$PEq =? Ker(FP)$

[1] Blass, A. et Gurevich, Y. Relations d'équivalence, invariants et formes normales . SIAM J. Comput. 13 (4): 682-689, 1984.

[2] Fortnow, L. et Grochow, JA Les classes de complexité des problèmes d'équivalence revisitées . Informer. et Comput. 209 (4): 748-763, 2011. Également disponible sur l' arxiv .

Le "représentant" doit-il être dans la classe d'équivalence?

Dans le cas contraire, prenez une hachage cryptographiquement forte fonction avec la résistance à la collision.$f$

Soit si f ( x ) = f ( y $x \simeq y$$f(x) = f(y)\,$. Il est facile de tester si deux choses sont équivalentes, mais si, étant donné , vous pouvez trouver une préimage canonique de h , alors vous pouvez trouver deux chaînes x et y telles que f ( x ) = f ( y $f(x) = h$$h$$x$$y$$f(x)=f(y)\,$. C'est censé être difficile (c'est ce que signifie la résistance aux collisions).

Bien sûr, les informaticiens ne peuvent pas prouver qu'il existe des fonctions de hachage cryptographiquement solides avec une résistance aux collisions, mais ils ont un certain nombre de candidats.

Tout d'abord, ce que vous demandez vraiment est généralement appelé un invariant complet. Une forme canonique ou normale requiert également que $f(x)$ soit équivalent à $x$ pour tout $x$ . (Demander un «représentant» est un peu ambigu, car certains auteurs pourraient vouloir dire que cela inclut la condition de forme canonique.)

Deuxièmement, veuillez pardonner l'autopromotion sans vergogne, mais c'est exactement l'une des questions sur lesquelles Fortnow et moi avons travaillé [1]. Nous avons montré que si chaque relation d'équivalence qui peut être décidée dans $\mathsf{P}$ aussi un invariant complet dans $\mathsf{FP}$ , alors de mauvaises choses se produisent. Il serait en particulier, impliquer $\mathsf{UP} \subseteq \mathsf{BQP}$ . Si une version promesse de cette affirmation est (voir théorème 4.6) puis $\mathsf{NP} \subseteq \mathsf{BQP} \cap \mathsf{SZK}$ et $\mathsf{PH} = \mathsf{AM}$ .

Maintenant, si vous voulez réellement une forme canonique (un représentant de chaque classe d'équivalence qui est également dans la classe d'équivalence), nous montrons que les choses se produisent encore pire. Autrement dit, si chaque relation d'équivalence décidable en temps polynomial a une forme canonique poly-temps, alors:

• Les nombres entiers peuvent être pris en compte dans le temps poly probabiliste
• Les fonctions de hachage sans collision qui peuvent être évaluées dans $\mathsf{FP}$ n'existent pas.
• $\mathsf{NP} = \mathsf{UP} = \mathsf{RP}$ (d'où$\mathsf{PH} = \mathsf{BPP}$ )

Il y a aussi des oracles qui vont dans les deux sens pour la plupart de ces déclarations sur les relations d'équivalence, dues à nous et à Blass et Gurevich [2].

Si au lieu de "n'importe quel" représentant, vous demandez l'élément lexicographiquement le moins dans une classe d'équivalence, trouver le plus petit élément lexicographiquement dans une classe d'équivalence peut être $NP$ -hard (en fait, $P^{NP}$ -hard) - même si la relation a une forme canonique en temps polynomial [2].

[1] Lance Fortnow et Joshua A. Grochow. Les classes de complexité des problèmes d'équivalence revisitées . Informer. et Comput. 209: 4 (2011), 748 à 763. Également disponible en arXiv: 0907.4775v2 .

[2] Andreas Blass et Yuri Gurevich. Relations d'équivalence, invariants et formes normales . SIAM J. Comput. 13: 4 (1984), 24-42.

Voici une tentative d'une autre réponse, où nous relâchons l'exigence sur le «représentant»; il ne doit pas nécessairement être membre de la classe d'équivalence, mais simplement une fonction identifiant la classe d'équivalence.

Supposons que vous ayez un groupe dans lequel vous pouvez effectuer des tests d'appartenance à un sous-groupe. Autrement dit, étant donné , vous pouvez vérifier si h est dans le sous-groupe généré par g 1 , … , g k .$g_1, g_2, \ldots, g_k$$h$$g_1, \ldots, g_k$

Prenez vos classes d'équivalence comme des ensembles d'éléments qui génèrent le même sous-groupe. Il est facile de vérifier si deux ensembles génèrent le même sous-groupe. Cependant, on ne sait pas du tout comment trouver un identifiant unique pour chaque sous-groupe. Je soupçonne que c'est vraiment un exemple si vous supposez des groupes de boîtes noires avec des tests d'appartenance à des sous-groupes. Cependant, je ne sais pas s'il existe un groupe non-oracle où ce problème semble être difficile.$g_1, g_2, \ldots, g_k$

Voici un exemple artificiel. Les objets sont des paires $(H,X)$ où $H$ est une formule SAT et $X$ est une affectation proposée aux variables. Dites $(H,X) \sim (H',X')$ si $H=H'$ et soit (a) $X$ et $X'$ sont tous deux des affectations satisfaisantes, soit (b) $X$ et $X'$ sont pas tous deux des affectations satisfaisantes. C'est réflexif, symétrique et transitif. Chaque insatisfiable$H$ a une classe d'équivalence composée de tous$(H,X)$ . Chaque$H$ satisfiablea une classe de tous$(H,X)$ où$X$ est une affectation satisfaisante, et une autre classe avec les non satisfaisantes.

Vérifier si $(H,X) \sim (H',X')$ est facile puisque nous vérifions que si $H=H'$ , alors si $X$ satisfait $H$ , alors si $X'$ satisfait $H$ . Mais pour calculer un membre canonique d'une classe donnée $(H,X)$ avec $H$ satisfait par $X$semble trop dur (je ne sais pas comment prouver au mieux la dureté). Nous pouvons facilement planter une solution supplémentaire aux instances SAT, donc connaître une solution ne nous aidera généralement pas à trouver une autre solution, et encore moins à en choisir une canonique. (Edit: ce que je veux dire, c'est que je ne m'attends à aucun algorithme efficace pour trouver des solutions supplémentaires étant donné une première solution. Parce que nous pourrions l'utiliser pour résoudre des problèmes SAT en "plantant" d'abord une solution supplémentaire dans le problème, puis en la nourrissant à l'algorithme. Voir les commentaires.)

C'est une question ouverte, au moins pour les graphiques. Je crois que les derniers progrès sont

Babai et Kucera, "Étiquetage canonique des graphiques en temps moyen linéaire", FOCS, 1979

qui donne un algorithme de temps linéaire (attendu) pour un graphe canonique qui est correct avec la probabilité $1 - \frac{1}{2^{O(n)}}$

Vous pouvez en savoir plus sur Wikipedia . Notez qu'une version dérandomisée de l'algorithme de Babai signifierait qu'il n'existe aucun exemple de ce type pour les graphiques.

Vérifier si deux circuits de taille circuits sont équivalents.$\leq N$

Pour déterminer si vous suffit d'évaluer aux 2 n points d'entrée. Pour déterminer un représentant de classe, il faudrait probablement tester tous les circuits possibles de 2 Ω ( N log N ) . Pour N suffisamment grand, cela est exponentiellement plus difficile que de tester l'équivalence du circuit.$C_1 \sim C_2$$2^n$$2^{\Omega(N \log N)}$$N$

A famous example from descriptive set theory:

Let us define an equivalence relation $\sim$ on $\mathbb R$ by

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.

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.