Ejemplo donde la equivalencia es fácil pero encontrar representante de clase es difícil

25

Supongamos que tenemos una clase de objetos (por ejemplo, gráficos, cadenas) y una relación de equivalencia en estos objetos. Para los gráficos esto podría ser isomorfismo gráfico. Para las cadenas, podríamos declarar dos cadenas equivalentes si son anagramas entre sí.

Estoy interesado en calcular un representante para una clase de equivalencia. Es decir, quiero una función f () tal que para dos objetos cualquiera x, y, f (x) = f (y) si f x e y son equivalentes. (*)

Para el ejemplo de anagramas, f (s) podría ordenar letras en la cadena, es decir. f ('cabac') = 'aabcc'. Para el isomorfismo gráfico, podríamos tomar f (G) como un gráfico G 'que es isomorfo a G y es el primer gráfico lexicoraphically en tener esta propiedad.

Ahora la pregunta: ¿Hay un ejemplo en el que el problema de determinar si dos elementos son equivalentes es "fácil" (tiempo polisoluble), mientras que encontrar un representante es difícil (es decir, no hay un algoritmo de tiempo polivinílico para calcular f () que satisfaga ( *)).

cc.complexity-theory Martin Pál
fuente

La pregunta puede ser demasiado general, ya que permite muchas construcciones "extrañas": tome un problema de NP completo y deje que cada instancia forme su propia clase de equivalencia. Para una instancia NO , establezca . Para un sí instancia , definir como el certificado lexicográficamente más pequeña.

s

$s$

f (s) = 0

$f(s)=0$

s

$s$

s

$s$

Gamow

2

@Gamow En su ejemplo, podría dejar que . Creo que el OP quiere un ejemplo donde no exista fácil .

f (s) = s

$f(s)=s$

f

$f$

Bjørn Kjos-Hanssen

44

Las palabras clave para la búsqueda son "canonización" o "etiquetado canónico".

Emil Jeřábek apoya a Monica el

Para aquellos confundidos como yo, aparentemente esta pregunta se volvió a publicar en 2018, y luego se notó y las respuestas se fusionaron aquí.

usul

25

Ok, ¿qué tal: los números e son equivalentes si , o ambos e tienen factorizaciones e donde , , y son primos y . Es decir: los productos de dos primos son equivalentes cuando comparten su factor primo más pequeño; otros números solo son equivalentes a ellos mismos. $x$ $y$ $x=y$ $x$ $y$ $x=pq$ $y=pr$ $p$ $q$ $r$ $p < \min(q,r)$

Es fácil probar si dos números diferentes son equivalentes: calcule su mcd, pruebe si no es trivial, pruebe si el mcd es menor que los cofactores, y pruebe si el mcd y sus cofactores son primos.

Pero no es obvio cómo calcular una función representativa en tiempo polinómico, y si agrega el requisito de que debe ser equivalente a entonces cualquier función representativa nos permitiría factorizar la mayoría de los productos de dos primos (cada uno que no sea es su propio representante). $f$ $f(x)$ $x$

David Eppstein
fuente

Re: "no es obvio cómo calcular una función representativa f ": Probablemente te estoy malinterpretando, pero: si x es el producto de dos primos distintos, entonces: que p sea el menor de estos primos; vamos s ser el menor primo después p ; elija f ( x ) = ps . Si x no es el producto de dos primos distintos, elija f ( x ) = x . (Todo lo cual es una forma indirecta de decir: elija f ( x ) = el elemento mínimo de la clase de equivalencia de x .) ¿No?

ruakh

2

@ruakh "Deje que sea el menor de estos números primos" supone que puede factorizar (para encontrar ), pero comúnmente se supone que es difícil.

p

$p$

x

$x$

p

$p$

Aaron Roth

@AaronRoth: Ah, ya veo. Por "no es obvio cómo calcular una función representativa ", debe haber querido decir algo así como "no es obvio cómo calcular fácilmente una función representativa ", entonces. Lo que encaja con la pregunta del OP. Eso tiene sentido, gracias. :-)

f

$f$

f

$f$

ruakh

Sí, lo siento, eso es lo que quise decir.

David Eppstein

21

Dos enteros mod son equivalentes si mod . Si uno pudiera calcular fácilmente un representante de clase para esta función, entonces se puede factorizar en tiempo polinómico probabilístico. $x,y$ $n$ $x^{2} \equiv y^{2}$ $n$

En general, tal ejemplo implicaría que . Supongamos que es una relación de equivalencia que es decidible en el tiempo polinómico. Luego, mediante la búsqueda lexicográfica utilizando un oráculo , se puede encontrar el elemento menos lexicográfico en la clase de equivalencia de cualquier cadena. Si , esto se convierte en tiempo polinómico, por lo que puede usar la cadena lexicográficamente menos equivalente como un representante de clase. Esta observación se debe originalmente a Blass y Gurevich [1]. $P \neq NP$ $R$ $NP$ $P=NP$

Tal ejemplo también implicaría (y por lo tanto, en particular, ). $UP \not\subseteq BQP$ $P \neq UP$

La pregunta que ha hecho es exactamente lo que denotamos en nuestro artículo con Lance Fortnow [2]. Ese documento también incluye los resultados que he establecido aquí, así como el ejemplo de las funciones hash señaladas por Peter Shor, algunos otros ejemplos posibles y los resultados y preguntas relacionados. $PEq =? Ker(FP)$

[1] Blass, A. y Gurevich, Y. Relaciones de equivalencia, invariantes y formas normales . SIAM J. Comput. 13 (4): 682-689, 1984.

[2] Fortnow, L. y Grochow, JA Clases de complejidad de problemas de equivalencia revisitados . Informar. y Comput. 209 (4): 748-763, 2011. También disponible en arxiv .

Joshua Grochow
fuente

15

¿El "representante" tiene que estar en la clase de equivalencia?

Si lo hace, entonces tome cualquier función hash criptográficamente fuerte con resistencia a la colisión. $f$

Deje si . Es fácil probar si dos cosas son equivalentes, pero si, dada , pudieras encontrar una preimagen canónica de , entonces podrías encontrar dos cadenas e tales que . Se supone que esto es difícil (eso es lo que significa resistencia a la colisión). $x \simeq y$ $f(x) = f(y)\,$ $f(x) = h$ $h$ $x$ $y$ $f(x)=f(y)\,$

Por supuesto, los informáticos no pueden demostrar que existen funciones hash criptográficamente fuertes con resistencia a colisiones, pero tienen varios candidatos.

Peter Shor
fuente

7

Primero, lo que realmente está pidiendo generalmente se llama invariante completo. Una forma canónica o normal también requiere que sea equivalente a para todas las . (Pedir un "representante" es un poco ambiguo, ya que algunos autores pueden querer decir que esto incluye la condición de forma canónica). $f(x)$ $x$ $x$

Segundo, perdona la descarada autopromoción, pero esta es exactamente una de las preguntas en las que Fortnow y yo trabajamos [1]. Mostramos que si cada relación de equivalencia que se puede decidir en también tiene una invariante completa en , entonces suceden cosas malas. En particular, implicaría . Si se cumple una versión prometedora de esta declaración (vea el Teorema 4.6), entonces y . $\mathsf{P}$ $\mathsf{FP}$ $\mathsf{UP} \subseteq \mathsf{BQP}$ $\mathsf{NP} \subseteq \mathsf{BQP} \cap \mathsf{SZK}$ $\mathsf{PH} = \mathsf{AM}$

Ahora, si realmente quieres una forma canónica (un representante de cada clase de equivalencia que también está en la clase de equivalencia), mostramos que suceden cosas aún peores. Es decir, si cada relación de equivalencia que se puede decidir en tiempo polinómico tiene una forma canónica de tiempo múltiple, entonces:

Los enteros se pueden factorizar en tiempo polivinílico probabilístico
Las funciones hash sin colisiones que se pueden evaluar en no existen. $\mathsf{FP}$
$\mathsf{NP} = \mathsf{UP} = \mathsf{RP}$ (de ahí ) $\mathsf{PH} = \mathsf{BPP}$

También hay oráculos en ambos sentidos para la mayoría de estas afirmaciones sobre relaciones de equivalencia, debido a nosotros y a Blass y Gurevich [2].

Si en lugar de "cualquier" representante, solicita el elemento lexicográficamente menos en una clase de equivalencia, encontrar el elemento lexicográficamente más pequeño en una clase de equivalencia puede ser duro (de hecho, -duro), incluso si el relación tiene una forma canónica de tiempo polinomial [2]. $NP$ $P^{NP}$

[1] Lance Fortnow y Joshua A. Grochow. Clases de complejidad de problemas de equivalencia revisitados . Informar. y Comput. 209: 4 (2011), 748-763. También disponible como arXiv: 0907.4775v2 .

[2] Andreas Blass y Yuri Gurevich. Relaciones de equivalencia, invariantes y formas normales . SIAM J. Comput. 13: 4 (1984), 24-42.

Joshua Grochow
fuente

Resultó que la versión de esta pregunta publicada en 2018 fue un reenvío por parte de un usuario de spam de una pregunta de 2012. ¿Quizás fusionar sus dos respuestas? Ambos mencionan UP y BQP pero de manera negada ... perderías algo de reputación, pero mitigaría parcialmente eso al votar tu respuesta anterior :)

Bjørn Kjos-Hanssen

5

Aquí hay un intento de otra respuesta, donde aflojamos el requisito del "representante"; en realidad no tiene que ser miembro de la clase de equivalencia, sino solo una función que identifica la clase de equivalencia.

Supongamos que tiene un grupo donde puede hacer pruebas de membresía de subgrupo. Es decir, dado , puede verificar si está en el subgrupo generado por . $g_1, g_2, \ldots, g_k$ $h$ $g_1, \ldots, g_k$

Tome sus clases de equivalencia como conjuntos de elementos que generan el mismo subgrupo. Es fácil verificar si dos conjuntos generan el mismo subgrupo. Sin embargo, no está nada claro cómo podría encontrar un identificador único para cada subgrupo. Sospecho que esto realmente es un ejemplo si asume grupos de caja negra con pruebas de membresía de subgrupos. Sin embargo, no sé si hay algún grupo no oráculo donde este problema parece ser difícil. $g_1, g_2, \ldots, g_k$

Peter Shor
fuente

4

Aquí hay un ejemplo artificial. Los objetos son pares donde es una fórmula SAT y es una asignación propuesta a las variables. Digamos si y (a) y son tareas satisfactorias, o (b) y son tareas satisfactorias. Esto es reflexivo, simétrico y transitivo. Cada insatisfactorio tiene una clase de equivalencia que consiste en todos . Cada satisfactoria tiene una clase de todos donde $(H,X)$ $H$ $X$ $(H,X) \sim (H',X')$ $H=H'$ $X$ $X'$ $X$ $X'$ $H$ $(H,X)$ $H$ $(H,X)$ $X$ es una tarea satisfactoria, y otra clase con las no satisfactorias.

Comprobar si es fácil ya que acabamos de comprobar si , entonces si satisface , entonces si satisface . Pero para calcular un miembro canónico de una clase dada con satisfecho por $(H,X) \sim (H',X')$ $H=H'$ $X$ $H$ $X'$ $H$ $(H,X)$ $H$ $X$ parece demasiado difícil (no estoy seguro de cómo probar mejor la dureza). Podemos plantar fácilmente una solución adicional para las instancias de SAT, por lo que conocer una solución generalmente no nos ayudará a encontrar otra solución, y mucho menos elegir una canónica. (Editar: lo que quiero decir es que no espero ningún algoritmo eficiente para encontrar soluciones adicionales dada una primera solución. Porque podríamos usarlo para resolver problemas de SAT al "plantar" primero una solución adicional en el problema, luego alimentarlo a el algoritmo. Ver comentarios.)

usul
fuente

Por "planta", ¿quiere decir algo como: dada una instancia de SAT en CNF, agreguemos una nueva variable no ocurra en y dejemos que ?

H = \underset{i}{⋀} φ_{i}

$H=\bigwedge_i\varphi_i$

p

$p$

H

$H$

K = \underset{i}{⋀} (φ_{i} \lor p)

$K = \bigwedge_i (\varphi_i\vee p)$

Bjørn Kjos-Hanssen

@ BjørnKjos-Hanssen, sí, algo así. Lo ideal sería crear exactamente una solución adicional. Así que creo que esto funciona (no en CNF): dada una fórmula genérica SAT , deje que donde son Las variables originales. Entonces, para aclarar, si tuviéramos un algoritmo para buscar / encontrar una segunda solución para las instancias de SAT, entonces, dado cualquier , construiríamos y lo alimentaríamos a ese algoritmo junto con la asignación verdadera y resolvería la instancia original . Si no me he perdido nada.

H

$H$

K = (H \land \neg p) \lor (p \land x_{1} \dots \land x_{n})

$K = (H \land \lnot p) \lor (p \land x_1 \cdots \land x_n)$

{x_{i}}

$\{x_i\}$

H

$H$

K

$K$

usul

Mientras que la palabra "representante" podría implicar que el codominio de debería ser su dominio, levantar esta restricción hace que esto no sea un ejemplo.

f

$f$

jix

1

(1) Encontrar una segunda asignación satisfactoria sigue siendo NP-difícil. (2) Encontrar un miembro canónico de la clase dada (H, X) en tiempo polinómico es equivalente a , que colapsa PH (Hemaspaandra-Naik-Ogihara-Selman). Sin embargo, tenga en cuenta que la pregunta en realidad no pide un miembro canónico de la clase, ya que no requiere que x sea equivalente a f (x), en realidad solo está pidiendo una invariante completa.

N P M V \subseteq_{c} N P S V

$NPMV \subseteq_c NPSV$

Joshua Grochow

4

Esta es una pregunta abierta, al menos para gráficos. Creo que el último progreso es

Babai y Kucera, "Etiquetado canónico de gráficos en tiempo lineal promedio", FOCS, 1979

que proporciona un algoritmo de tiempo lineal (esperado) para un gráfico canónico que es correcto con probabilidad $1 - \frac{1}{2^{O(n)}}$

Puedes leer más en Wikipedia . Tenga en cuenta que una versión desaleatorizada del algoritmo de Babai significaría que no existe tal ejemplo para los gráficos.

Stella Biderman
fuente

2

También de interés: para las formas canónicas en el peor de los casos en lugar del caso promedio, el reciente artículo de Schweitzer-Wiebking ( arxiv.org/abs/1806.07466 ) ofrece una técnica que ofrece buenas formas canónicas para muchas relaciones de equivalencia relacionadas (equivalencia de código, permutación conjugación de grupo, isografía de hipergrafía), y en su sección final sugieren que sus técnicas podrían aplicarse también al resultado de Babai, dando una forma canónica cuasi-poli-tiempo para IG.

Joshua Grochow

@JoshuaGrochow No escuché sobre esto, pero eso es muy emocionante. Guardando para leer más tarde.

Stella Biderman

2

Prueba de si dos circuitos de tamaño circuitos son equivalentes. $\leq N$

Para determinar si solo necesita evaluar en los puntos de entrada. Para determinar un representante de clase, uno probablemente tendría que probar todos los circuitos posibles . Para suficientemente grande, esto es exponencialmente más difícil que probar la equivalencia del circuito. $C_1 \sim C_2$ $2^n$ $2^{\Omega(N \log N)}$ $N$

David Harris
fuente

Aquí hay una función que asigna cada circuito a un objeto representativo (no un circuito) tan rápido como las pruebas de equivalencia: asigna cada circuito al vector de salidas para cada posible entrada. Probablemente no sería difícil convertir esto en un circuito de estilo de barra transversal explícito.

f

$f$

2^{n}

$2^n$

David Eppstein

Insistí en que los circuitos tenían un tamaño acotado para evitar una asignación fácil de salidas al circuito. Sin embargo, supuse que la función necesitaba asignarse a un representante de clase en lugar de una cadena arbitraria.

2^{n}

$2^n$

f

$f$

David Harris

1

Un famoso ejemplo de la teoría de conjuntos descriptiva:

Definamos una relación de equivalencia en por $\sim$ $\mathbb R$

r \sim s ⟺ r - s \in Q .

$r\sim s\iff r-s\in\mathbb Q.$

Esta es una relación de equivalencia bastante "fácil", en particular es medible.

Pero encontrar representantes equivale a encontrar un conjunto Vitali , que requiere el Axioma de Elección y no puede ser medible.

Bjørn Kjos-Hanssen
fuente

0

Deje que los objetos en su universo sean los triples ( donde sea un problema de Satisfacción, en las variables , es 0 o 1, e es un cadena de bits de longitud , donde . Es decir, es una asignación a que satisface si es 1 o no satisface si es 0. $\Phi, b, i)$ $\Phi$ $x_0, \ldots, x_{k-1}$ $b$ $i$ $k$ $\Phi(i)=b$ $i$ $x_0, \ldots, x_k$ $\Phi$ $b$ $\Phi$ $b$

Dos objetos son equivalentes si tienen la misma . Fácil de verificar. $\Phi$

Deje que el objeto representativo sea el más lexicográfico entre todos en la clase de equivalencia.

El representante es NP-complete para encontrar: resolvería SAT, ya que si el mayor lexicográficamente tiene , entonces es insatisfactorio; si tiene , es satisfactoria. $b=0$ $\Phi$ $b=1$

Parece que la mayoría de los problemas con NP completo se pueden plantear de esta manera; se trata de colocar el certificado de membresía en la codificación del elemento.

Pensé que tal vez era un problema de tarea, por eso no publiqué la solución antes. Yo debí haber hecho; Podría haber usado esos puntos que recibió @ david-eppstien. Dios sabe que no los necesita.

Gara Pruesse
fuente

1

Ah, pero en este caso hay una opción fácil de representante: simplemente tome como cualquier cosa como .

i

$i$

b

$b$

Φ (i)

$\Phi(i)$

Bjørn Kjos-Hanssen

-3

Supongo que puede lograrlo fácilmente para prácticamente cualquier problema del tipo que describe.

Ejemplo trivial: supongamos que los objetos son cadenas, y cualquier es equivalente solo a sí misma. Determinar si dos elementos son equivalentes siempre es fácil (es simplemente igualdad). Sin embargo, puede definir como su función dura inyectiva favorita. $x$ $f()$

MCH
fuente

3

Pero en el caso que describa, hay una diferente que es fácil de calcular: la función de identidad.

f

$f$

David Eppstein

De la pregunta, no está claro si se requiere la dureza de todas las , en lugar de algunas .

f

$f$

f

$f$

MCH

3

@MCH Creo que está perfectamente claro, ya que de lo contrario no habría ninguna duda y la pregunta sería tonta.

Random832

Ejemplo donde la equivalencia es fácil pero encontrar representante de clase es difícil

Respuestas: