Qual é o algoritmo mais eficiente para decidir se um elemento é o menor em sua órbita?

Dado um grupo agindo em um conjunto com uma ordem total e , qual é o algoritmo mais eficiente para decidir se x é ou não o menor elemento em sua órbita, ou seja, decidir se ? $G$ $X$ $\leq$ $x\in X$ $min(Gx) = x$

Minha motivação vem da solução SMT, onde houve algum interesse em quebrar automaticamente as simetrias. A adição de predicados de quebra de simetria geralmente resulta em um grande conjunto de cláusulas, portanto, estou interessado na possibilidade de lidar com isso como uma propagação da teoria preguiçosa.

A descrição acima é talvez muito geral e, como observado por sid , NP-hard. Uma possível tarefa mais simples é, dado um grupo de permutações de cadeias de comprimento codificadas como um conjunto de geradores e uma cadeia de comprimento . Qual é o algoritmo mais eficiente para decidir se essa string é a menor lexicograficamente em sua órbita? $n$ $x$ $n$

ds.algorithms gr.group-theory HaskellElephant
fonte

Presumo que você esteja falando de conjuntos finitos X? Eu acho que decidir isso é difícil. Seja

um tour por um conjunto de cidades no problema do Vendedor ambulante com

. Seja o grupo

o grupo simétrico

. Então a órbita é todos os roteiros possíveis e provar que um deles é mínimo é difícil para NP.

X = {c_{1}, \dots, c_{n}}

$X=\{c_1,\dots,c_n\}$

c_{1} \to c_{2} \dots

$c_1 \rightarrow c_2 \dots$

G

$G$

S_{n}

$S_n$

Opte

@ Sid, sim, eu só estou interessado no caso em que X é finito, e eu não tinha pensado nisso, mas certamente é NP-difícil. Eu acho que ainda pode haver a possibilidade de um algoritmo eficiente de monte carlo.

precisa saber é o seguinte

Embora se você usar um critério diferente para o mínimo, é polinomial aqui: é fácil encontrar o passeio lexicograficamente menor (pelo menos se você assumir que todas as bordas têm rótulos diferentes; caso contrário, ainda é NP).

Peter Shor

@ PeterShor, sim, de fato, para o meu propósito, qualquer forma canônica serve.

precisa saber é o seguinte

são apresentados como oráculos de valor, isto requer enumerando

G

$G$

X

$X$

G

$G$

David Harris

Para as relações de equivalência geral, não aquelas que resultam de ações do grupo de permutação, mesmo encontrar lexicograficamente menos ainda é "muito" geral. Encontrando-se o lexicograficamente menor elemento em uma classe de equivalência pode ser -Hard (na verdade, -Hard) - mesmo que a relação tem uma forma canónica de tempo polinomial [1]. $NP$ $P^{NP}$

No entanto, para os problemas órbita grupo permutação como descrever, decidir se os dois pontos estão no mesmo órbita não é provável que seja -Hard: é em , e, portanto, não -Hard a menos que o a hierarquia polinomial cai para o segundo nível. $NP$ $NP \cap coAM$ $NP$

Uma forma canônica para isomorfismo de gráfico também é um caso especial do segundo problema que você declara. A forma canônica mais conhecida para isomorfismo gráfico é executada no tempo [2]. $2^{\tilde{O}(\sqrt{n})}$

Como você disse nos comentários que qualquer forma canônica serve, você também pode estar interessado no meu artigo com Lance Fortnow [3]: em sua atual generalidade, acho que sua pergunta está relacionada aos nossos resultados. Mostramos que, se cada equivalência relação decidable em tem uma forma canônica em , em seguida, "maus" consequências resultar, como , que, em particular, implica que a hierarquia polinomial cai para baixo para . Por outro lado, as relações de equivalência em que você está interessado podem não estar em $P$ $P$ $NP = UP = RP$ $BPP$ $P$ , mas esse resultado sugere que, mesmo que se encontre em uma classe de maior complexidade, outros problemas difíceis ainda podem ficar no seu caminho.

Então, eu acho que se você quer melhores limites superiores, realmente precisa que o problema seja mais específico.

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

[2] László Babai e Eugene M. Luks. Rotulagem canônica de gráficos . STOC 1983, 171-183.

[3] 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 .

Joshua Grochow
fonte

GI no tempo poli implica

no seu trabalho? O que implicaria esse resultado (quaisquer problemas completos) e o que separaria?

P E q = C F

$PEq=CF$

T ....

Não tão longe quanto o que sei. Na melhor das hipóteses, isso implicaria que qualquer problema de isomorfismo combinatório está em Ker (FP); uma questão é que uma forma canônica para um gráfico não precisa produzir uma forma canônica para a estrutura com a qual você começou; a outra questão é que o isomorfismo combinatório não é necessariamente completo com PEq. Perguntamos se havia problemas de PEq-completo; Finkelstein e Hescott mostraram problemas com CEq-completo para C mais alto na HP, mas deixaram em aberto a questão da existência de problema com PEq-completo.

Joshua Grochow 07/12/2015

seria possível que a existência de um problema completo no PEq implique colapsos de PH em algum nível?

T ....

@ Turbo: Claro, embora pareça um pouco improvável para mim. Você conhece algum exemplo em que a existência de um problema completo para alguma classe implique colapsos de PH? (Além dos problemas com PH completo). Acho que é provável que (a) problemas com PEq existam (e não contradigam conjecturas importantes), apenas não descobrimos como construí-los, ou (b) existem existem oráculos nos dois sentidos quanto à existência de problemas completos com PEq. (b) me parece mais provável - por analogia com o BPP - porque o PEq é essencialmente uma classe semântica.

Joshua Grochow

Qual é o algoritmo mais eficiente para decidir se um elemento é o menor em sua órbita?

Respostas: