Probabilidade de gerar uma permutação desejada por swaps aleatórios

Estou interessado no seguinte problema. Recebemos como entrada uma "permutação de destino" , bem como uma lista ordenada de índices . Então, começando com a lista (ou seja, a permutação de identidade), a cada passo , trocamos o elemento em $\sigma\in S_n$ $i_1,\ldots,i_m\in [n-1]$ $L=(1,2,\ldots,n)$ $t\in [m]$ $i_t^{th}$ $L$ com o elemento, com probabilidade independente . Seja a probabilidade de que seja produzido como saída. $(i_t+1)^{st}$ $1/2$ $p$ $\sigma$

Gostaria de saber (qualquer um) o seguinte:

É decidir se um problema -completo? $p>0$ $NP$
O cálculo de exatamente completo? $p$ $\#P$
O que podemos dizer sobre a aproximação de a uma constante multiplicativa? Existe um PTAS para isso? $p$

A variante em que os swaps não precisam ser de elementos adjacentes também é interessante.

Observe que não é difícil reduzir esse problema para caminhos separados por arestas (ou para o fluxo multicomodidade com valor inteiro); o que eu não sei é uma redução na outra direção.

Atualização: OK, verificando a Garey & Johnson, o problema deles [MS6] ("Permutation Generation") é o seguinte. Dado como entrada um alvo de permutação , em conjunto com subconjuntos , decidir se é expresso como um produto , onde cada actua trivialmente de nem todos os índices em . Garey, Johnson, Miller e Papadimitriou (atrás de um paywall, infelizmente) provam que esse problema é $\sigma\in S_n$ $S_1,\ldots,S_m\in [n]$ $\sigma$ $\tau_1 \cdots \tau_m$ $\tau_i$ $S_i$ -hard. $NP$

$p>0$ $NP$ $S_1,S_2,\ldots$ $S_i$ $S_i$ $\sigma$ $\tau_1 \cdots \tau_m$

$\#P$ $P=NP$

np-hardness counting-complexity permutations sorting-network disjoint-paths Scott Aaronson
fonte

Não tenho certeza se entendi a pergunta. De onde vem a probabilidade? Você troca com probabilidade 1/2 e não com probabilidade 1/2?

Arnab

| S_{i} | = 2

$|S_i|=2$

Respostas:

Eu acho que se p> 0 pode ser decidido em tempo polinomial.

O problema em questão pode ser facilmente convertido como o problema de caminhos separados por arestas, em que o gráfico subjacente é um gráfico planar composto por m +1 camadas, cada uma das quais contém n vértices, mais m grau-4 vértices para representar os possíveis swaps adjacentes. Observe que a planaridade deste gráfico decorre do fato de permitirmos apenas swaps adjacentes.

Se não me engano, isso ocorre no caso especial do problema de caminhos disjuntos resolvidos por Okamura e Seymour [OS81]. Além disso, Wagner e Weihe [WW95] fornecem um algoritmo de tempo linear para este caso.

Veja também as notas da aula de Goemans [Goe12], que oferecem uma boa exposição do teorema de Okamura-Seymour e do algoritmo Wagner-Weihe.

Referências

Michel X. Goemans. Notas da palestra, 18.438 Otimização combinatória avançada, Palestra 23 . Instituto de Tecnologia de Massachusetts, primavera de 2012. http://math.mit.edu/~goemans/18438S12/lec23.pdf

[OS81] Haruko Okamura e Paul D. Seymour. Fluxos multicomodidades em gráficos planares. Journal of Combinatorial Theory, Série B , 31 (1): 75–81, agosto de 1981. http://dx.doi.org/10.1016/S0095-8956(81)80012-3

[WW95] Dorothea Wagner e Karsten Weihe. Um algoritmo de tempo linear para caminhos separados por arestas em gráficos planares. Combinatorica , 15 (1): 135–150, março de 1995. http://dx.doi.org/10.1007/BF01294465

Tsuyoshi Ito
fonte