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

10

Estou interessado no seguinte problema. Recebemos como entrada uma "permutação de destino" , bem como uma lista ordenada de índices i 1 , , i m[ n - 1 ] . Então, começando com a lista L = ( 1 , 2 , , n ) (ou seja, a permutação de identidade), a cada passo t [ m ] , trocamos o elemento i t h t em LσSni1,,im[n1]L=(1,2,,n)t[m]itthLcom o elemento, com probabilidade independente 1 / 2 . Seja p a probabilidade de que σ seja produzido como saída.(it+1)st1/2pσ

Gostaria de saber (qualquer um) o seguinte:

  • É decidir se um N P problema -completo?p>0NP
  • O cálculo de exatamente # P 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 S 1 , ... , S m[ n ] , decidir se σ é expresso como um produto τ 1τ m , onde cada τ i actua trivialmente de nem todos os índices em S i . Garey, Johnson, Miller e Papadimitriou (atrás de um paywall, infelizmente) provam que esse problema é NσSnS1,,Sm[n]στ1τmτiSi -hard.NP

p>0NPS1,S2,SiSiστ1τm

#PP=NP

Scott Aaronson
fonte
11
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
|Si|=2

Respostas:

15

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