Exemplo em que a equivalência é fácil, mas é difícil encontrar o representante da classe

Suponha que tenhamos uma classe de objetos (digamos gráficos, seqüências de caracteres) e uma relação de equivalência nesses objetos. Para gráficos, isso pode ser isomorfismo gráfico. Para strings, poderíamos declarar duas strings equivalentes se forem anagramas uma da outra.

Estou interessado em calcular um representante para uma classe de equivalência. Ou seja, eu quero uma função f () tal que para quaisquer dois objetos x, y, f (x) = f (y) se x e y forem equivalentes. (*)

Para o exemplo de anagramas, f (s) pode classificar letras na string, ie. f ('cabac') = 'aabcc'. Para o isomorfismo do gráfico, poderíamos considerar f (G) como um gráfico G 'isomórfico para G e é o primeiro gráfico lexicoraphically a ter essa propriedade.

Agora, a pergunta: existe um exemplo em que o problema de determinar se dois elementos são equivalentes é "fácil" (solucionável em tempos poligonais), enquanto é difícil encontrar um representante (por exemplo, não há algoritmo de tempo polimétrico para calcular f () que satisfaça ( *)).

Ok, como cerca de: números e são equivalentes se quer , ou ambos e têm fatorações e onde , , e são todos nobre e . Ou seja: produtos de dois primos são equivalentes quando compartilham seu menor fator primo; outros números são equivalentes apenas a si mesmos.y x = y x y x = p q y = p r p q r p < min ( q , r $x$$y$$x=y$$x$$y$$x=pq$$y=pr$$p$$q$$r$$p < \min(q,r)$

É fácil testar se dois números diferentes são equivalentes: calcular seu gcd, testar se não é trivial, testar se o gcd é menor que os cofatores e testar se o gcd e seus cofatores são primos.

Mas não é óbvio como calcular uma função representativa em tempo polinomial, e se você adicionar o requisito de que deve ser equivalente a , qualquer função representativa nos permitirá fatorar a maioria dos produtos de dois primos (cada um que é n representante próprio).f ( x ) $f$$f(x)$$x$

Dois inteiros mod são equivalentes se mod . Se alguém puder calcular facilmente um representante de classe para esta função, o fatoramento pode ser feito em tempo polinomial probabilístico.$x,y$$n$$x^{2} \equiv y^{2}$$n$

Em geral, esse exemplo implicaria que . Suponha que$P \neq NP$$R$ seja uma relação de equivalência decidível em tempo polinomial. Então por pesquisa lexicográfica utilizando uma oráculo, pode-se encontrar o lexicographically menos elemento na classe de equivalência de qualquer string. Se P = N P , isso se torna tempo polinomial, para que você possa usar a cadeia lexicograficamente menos equivalente como representante de classe. Esta observação é originalmente devida a Blass e Gurevich [1].$NP$$P=NP$

P ≠ U $UP \not\subseteq BQP$$P \neq UP$

A pergunta que você fez é exatamente o que denotamos em nosso artigo com Lance Fortnow [2]. Esse documento também inclui os resultados que afirmei aqui, bem como o exemplo de funções de hash apontadas por Peter Shor, alguns outros exemplos possíveis e resultados e perguntas relacionadas.$PEq =? Ker(FP)$

[1] Blass, A. e Gurevich, Y. Relações de equivalência, invariantes e formas normais . SIAM J. Comput. 13 (4): 682-689, 1984.

[2] Fortnow, L. e Grochow, JA Classes de complexidade de problemas de equivalência revisitadas . Informar. e Comput. 209 (4): 748-763, 2011. Também disponível no arxiv .

O "representante" precisa estar na classe de equivalência?

Se isso acontecer, então tomar qualquer hash criptograficamente forte função com a resistência à colisão.$f$

Seja se ,. É fácil testar se duas coisas são equivalentes, mas se, dado , você puder encontrar uma pré-imagem canônica de , poderá encontrar duas cadeias e modo que ,. Isso deveria ser difícil (é isso que significa resistência à colisão).f ( x ) = f ( y $x \simeq y$$f(x) = f(y)\,$h x y f ( x ) = f ( y $f(x) = h$$h$$x$$y$$f(x)=f(y)\,$

Obviamente, os cientistas da computação não podem provar que existem funções hash criptograficamente fortes com resistência à colisão, mas eles têm vários candidatos.

Primeiro, o que você realmente está pedindo é normalmente chamado de invariante completo. Uma forma canônica ou normal também requer que seja equivalente a para todos os . (Pedir um "representante" é um pouco ambíguo, pois alguns autores podem significar que isso inclui a condição de forma canônica.)$f(x)$$x$$x$

Segundo, por favor, perdoe a autopromoção desavergonhada, mas essa é exatamente uma das perguntas em que Fortnow e eu trabalhamos [1]. Mostramos que se toda relação de equivalência que pode ser decidida em também tiver um invariante completo em , coisas ruins acontecem. Em particular, isso implicaria . Se uma versão promissora desta declaração for válida (consulte o Teorema 4.6), então e .$\mathsf{P}$$\mathsf{FP}$$\mathsf{UP} \subseteq \mathsf{BQP}$$\mathsf{NP} \subseteq \mathsf{BQP} \cap \mathsf{SZK}$$\mathsf{PH} = \mathsf{AM}$

Agora, se você realmente deseja uma forma canônica (um representante de cada classe de equivalência que também está na classe de equivalência), mostramos coisas ainda piores. Ou seja, se todas as relações de equivalência decidíveis no tempo polinomial tiverem uma forma canônica no tempo polinominal, então:

• Inteiros podem ser fatorados em tempo poli probabilístico
• Funções hash sem colisão que podem ser avaliadas em não existem.$\mathsf{FP}$
• $\mathsf{NP} = \mathsf{UP} = \mathsf{RP}$ (daí )$\mathsf{PH} = \mathsf{BPP}$

Também existem oráculos nos dois sentidos para a maioria dessas afirmações sobre relações de equivalência, devido a nós e a Blass e Gurevich [2].

Se, em vez de "qualquer" representante, você solicitar o elemento lexicograficamente menos em uma classe de equivalência, encontrar o elemento lexicograficamente menor em uma classe de equivalência pode ser -hard (na verdade, -hard) - mesmo se o o relacionamento tem uma forma canônica em tempo polinomial [2].$NP$$P^{NP}$

[1] Lance Fortnow e Joshua A. Grochow. Classes de complexidade dos problemas de equivalência revisitados . Informar. e Comput. 209: 4 (2011), 748-763. Também disponível como arXiv: 0907.4775v2 .

[2] Andreas Blass e Yuri Gurevich. Relações de equivalência, invariantes e formas normais . SIAM J. Comput. 13: 4 (1984), 24-42.

Aqui está uma tentativa de outra resposta, onde afrouxamos o requisito do "representante"; na verdade, ele não precisa ser um membro da classe de equivalência, mas apenas uma função que identifica a classe de equivalência.

Suponha que você tenha um grupo em que possa realizar testes de associação de subgrupos. Ou seja, dado , é possível verificar se h está no subgrupo gerado por g 1 , … , g k .$g_1, g_2, \ldots, g_k$$h$$g_1, \ldots, g_k$

Considere suas classes de equivalência como conjuntos de elementos que geram o mesmo subgrupo. É fácil verificar se dois conjuntos geram o mesmo subgrupo. No entanto, não está claro como você pode encontrar um identificador exclusivo para cada subgrupo. Suspeito que esse seja realmente um exemplo se você assumir grupos de caixas negras com teste de associação a subgrupos. No entanto, não sei se existe algum grupo não oráculo em que esse problema pareça difícil.$g_1, g_2, \ldots, g_k$

Aqui está um exemplo artificial. Os objetos são pares $(H,X)$ que $H$ é uma fórmula SAT e $X$ é uma atribuição proposta para as variáveis. Diga $(H,X) \sim (H',X')$ se $H=H'$ e (a) $X$ e $X'$ são tarefas satisfatórias, ou (b) $X$ e $X'$ não são tarefas satisfatórias. Isso é reflexivo, simétrico e transitivo. Cada insatisfatório$H$ tem uma classe de equivalência composta por todos$(H,X)$ . Cada$H$ satisfatóriotem uma classe de todos$(H,X)$ onde$X$ é uma tarefa satisfatória, e outra classe com as não satisfatórias.

Verificar se $(H,X) \sim (H',X')$ é fácil, uma vez que apenas verificar se $H=H'$ , em seguida, se $X$ satisfaz $H$ , em seguida, se $X'$ satisfaz $H$ . Mas para calcular um membro canônico de uma classe dada $(H,X)$ com $H$ satisfeito por $X$parece muito difícil (não sei qual a melhor forma de provar a dureza). Podemos facilmente plantar uma solução extra para instâncias do SAT, portanto, conhecer uma solução geralmente não nos ajuda a encontrar outra solução, muito menos escolher uma solução canônica. (Edit: O que quero dizer é que não espero nenhum algoritmo eficiente para encontrar soluções adicionais, dada uma primeira solução. Porque poderíamos usá-lo para resolver problemas de SAT, primeiro "plantando" uma solução extra no problema e alimentando-o para o algoritmo. Ver comentários.)

Esta é uma pergunta em aberto, pelo menos para gráficos. Eu acredito que o progresso mais recente é

Babai e Kucera, "Rotulagem canônica de gráficos em tempo médio linear", FOCS, 1979

$1 - \frac{1}{2^{O(n)}}$

Você pode ler mais na Wikipedia . Observe que uma versão derandomizada do algoritmo de Babai significaria que não existe exemplo para gráficos.

$\leq N$

$C_1 \sim C_2$$2^n$$2^{\Omega(N \log N)}$$N$

Um exemplo famoso da teoria descritiva dos conjuntos:

$\sim$$\mathbb R$

Esta é uma relação de equivalência bastante "fácil", em particular é mensurável.

Mas encontrar representantes equivale a encontrar um conjunto Vitali , que requer o Axioma da Escolha e não pode ser mensurável.

$\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$

$\Phi$

Seja o objeto representativo o maior lexicograficamente entre todos na classe de equivalência.

$b=0$$\Phi$$b=1$

Parece que a maioria dos problemas de NP-completos pode ser colocada dessa maneira; é uma questão de colocar o certificado de associação na codificação do elemento.

Achei que talvez fosse um problema de lição de casa, e é por isso que não publiquei a solução anteriormente. Eu deveria ter feito; Eu poderia ter usado aqueles pontos que @ david-eppstien conseguiu. Deus sabe, ele não precisa deles.

Suponho que você consiga isso facilmente para praticamente qualquer problema do tipo que você descreve.

$x$$f()$