Probabilidad de generar una permutación deseada mediante intercambios aleatorios

10

Estoy interesado en el siguiente problema. Se nos da como entrada una "permutación de destino" , así como una lista ordenada de índices . Luego, comenzando con la lista (es decir, la permutación de identidad), en cada paso de tiempo intercambiamos el elemento en con el elemento, con probabilidad independiente . Sea la probabilidad de que se produzca como salida.σSnortei1,,im[n1]L=(1,2,,n)t[m]itthL(it+1)st1/2pσ

Me gustaría saber (cualquiera de) lo siguiente:

  • ¿Decidir si un completo?N Pp>0NP
  • ¿Calcular exactamente # P -completo?p#P
  • ¿Qué podemos decir acerca de aproximar a una constante multiplicativa? ¿Hay un PTAS para esto?p

La variante donde los intercambios no necesitan ser elementos adyacentes también es de interés.

Tenga en cuenta que no es difícil reducir este problema a rutas de disyunción de borde (o al flujo multicommodity con valor entero); Lo que no sé es una reducción en la otra dirección.

Actualización: OK, comprobando Garey & Johnson, su problema [MS6] ("Generación de permutación") es el siguiente. Dada como entrada una permutación objetivo , junto con los subconjuntos S 1 , ... , S m[ n ] , decida si σ es expresable como un producto τ 1τ m , donde cada τ i actúa trivialmente en todos los índices no en S i . Garey, Johnson, Miller y Papadimitriou (detrás de un muro de pago, desafortunadamente) prueban que este problema es NσSnS1,,Sm[norte]στ1τmetroτyoSyo duro.nortePAG

Si los swaps no necesitan ser adyacentes, entonces creo que esto implica que decidir si también es N P -hard. La reducción es simplemente esto: para cada S 1 , S 2 , ... en orden, ofreceremos un conjunto de "intercambios candidatos" que corresponde a una red de clasificación completa en S i (es decir, capaz de permutar S i arbitrariamente, mientras que actuando trivialmente en todo lo demás). Entonces σ será expresable como τ 1τ m , si y solo si es accesible como producto de estos intercambios.pag>0 0nortePAGS1,S2,...SyoSyoστ1τmetro

Esto todavía deja abierta la versión "original" (donde los intercambios son de elementos adyacentes solamente). Para la versión de conteo (con intercambios arbitrarios), por supuesto, sugiere fuertemente que el problema debería ser -completo. En cualquier caso, se descarta un PTAS a menos que P = N P .# #PAGPAG=nortePAG

Scott Aaronson
fuente
1
No estoy seguro de entender la pregunta. ¿Dónde entra la probabilidad? ¿Es que intercambias con probabilidad 1/2 y no con probabilidad 1/2?
arnab
@arnab sí. Scott, entonces has demostrado eso con , todavía es NP-hard. Mi intuición es que tu problema "original" debería ser más fácil, pero primero trataría de jugar con la reducción del papel. El |SyoEl |=2
didest

Respuestas:

15

Creo que si p> 0 se puede decidir en tiempo polinómico.

El problema en cuestión se puede convertir fácilmente como el problema de caminos de borde disjunto, donde el gráfico subyacente es un gráfico plano que consta de m +1 capas, cada una de las cuales contiene n vértices, más m vértices de grado 4 para representar los posibles intercambios adyacentes. Tenga en cuenta que la planaridad de este gráfico se deriva del hecho de que solo permitimos intercambios adyacentes.

Si no me equivoco, esto recae en el caso especial del problema de caminos de disyunción de borde resuelto por Okamura y Seymour [OS81]. Además, Wagner y Weihe [WW95] ofrecen un algoritmo de tiempo lineal para este caso.

Véanse también las notas de conferencia de Goemans [Goe12], que ofrece una buena exposición del teorema de Okamura-Seymour y el algoritmo de Wagner-Weihe.

Referencias

[Goe12] Michel X. Goemans. Notas de la clase, 18.438 Optimización combinatoria avanzada, clase 23 . Instituto de Tecnología de Massachusetts, primavera de 2012. http://math.mit.edu/~goemans/18438S12/lec23.pdf

[OS81] Haruko Okamura y Paul D. Seymour. Los flujos de productos múltiples en gráficos planos. Journal of Combinatorial Theory, Serie B , 31 (1): 75–81, agosto de 1981. http://dx.doi.org/10.1016/S0095-8956(81)80012-3

[WW95] Dorothea Wagner y Karsten Weihe. Un algoritmo de tiempo lineal para rutas de disyunción de borde en gráficos planos. Combinatorica , 15 (1): 135–150, marzo de 1995. http://dx.doi.org/10.1007/BF01294465

Tsuyoshi Ito
fuente