Calcular la paridad de una permutación de una manera de transmisión continua

Estoy buscando un algoritmo de una pasada que calcule la paridad de una permutación. Supongo que una permutación de entrada viene dada por la secuencia $\pi[1], \pi[2], \cdots, \pi[n]$ . La salida debe ser la paridad de la permutación. La pregunta que me interesa es cuánta memoria debe usar un algoritmo determinista. ¿Hay algún algoritmo aleatorio para el problema?

Sé que calcular el número de inversiones en una pasada usa memoria . El límite superior se puede obtener fácilmente con cualquier BST. El límite inferior se presenta aquí: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622 $\Theta(n)$

Por desgracia, la prueba del límite inferior en el documento no puede extenderse al caso de paridad (o no es tan obvio para mí).

También sé que la paridad informática en un espacio pequeño con acceso aleatorio a una permutación se puede hacer en tiempo y memoria mediante algoritmo determinista o en tiempo y memoria aleatoria. Ver http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256 $O(n \log n)$ $O(\log^2 n)$ $O(n \log n)$ $O(\log n)$

La idea principal es que la paridad de una permutación se puede calcular mediante la fórmula , donde es el número de ciclos es el tamaño. Los autores realizan el ciclo de descomposición de una permutación. Entonces uno puede calcular fácilmente el número de ciclos. $sgn(\pi) = (-1)^{n - c}$ $c$ $n$

¿Alguien conoce un algoritmo efectivo o límite inferior en la memoria para calcular la paridad en el modelo de transmisión? Los algoritmos aleatorios mejores que las monedas aleatorias también me interesan.

ds.algorithms permutations streaming-algorithms Vsevolod Oparin
fuente

Es interesante. ¿Podría dibujar una prueba o nombrar un problema que reduzca a paridad?

Vsevolod Oparin

@ András: ¿No funciona un algoritmo de espacio O (n) simplemente haciendo un seguimiento de los elementos que ya se han visto (digamos en un vector de bits), y luego para cada nuevo elemento x agregando la paridad del # de todavía-a- ser visto elementos más pequeños que x?

László Kozma

@laszlo su límite superior

ahora me parece más convincente que mi argumento a favor de un límite inferior más grande.

O (n)

$O(n)$

András Salamon

Un resultado negativo para el límite inferior. Los autores de la primera papel proporciona permutación

basado en dos conjuntos

. Lo usan para calcular si

cruzan. La paridad informática de la permutación requiere solo 3 bits de comunicación unidireccional. Se puede obtener fácilmente calculando el rango de la matriz correspondiente.

π = \bar{A_{0}} B_{1} A_{0} \bar{B_{1}}

$\pi = \bar{A_0}B_1A_0\bar{B_1}$

A

$A$

B

$B$

A

$A$

B

$B$

Vsevolod Oparin

Relacionado: stackoverflow.com/questions/20702782/…

domotorp

Respuestas:

Me gustaría pedirles a todos que no voten esto, ya que esta no es una respuesta, sino un comentario extendido, en el que me gustaría argumentar por qué esta pregunta no recibió ninguna respuesta. Mi punto principal es que un límite inferior de complejidad de comunicación no funcionará. Con esto quiero decir que no importa cómo cortamos la entrada en dos partes y se la damos a dos jugadores, A y B, A puede transferir un solo bit a B desde el cual puede calcular la paridad de la permutación. (Esto sigue simplemente considerando inversiones).

Las pruebas que usan otro límite son difíciles. Vea este comentario aquí de Noam Nisan (para la versión no determinista): limita el tamaño del NFA más pequeño para L_k-distinct ,

Hermann Gruber respondió a esta pregunta relacionada, que muestra que el límite inferior de la complejidad de la comunicación puede estar muy lejos de la verdad (nuevamente en la versión no determinista). Límite inferior para NFA que acepta lenguaje de 3 letras .

También relacionado con que decidir si la permutación es un ciclo único, parece ser difícil, vea este documento de FOCS de Ran Raz y Boris Spieker: http://www.computer.org/csdl/proceedings/focs/1993/4370/00 /0366870-abs.html .

Entonces, también estoy muy interesado en conocer la respuesta a esta pregunta.

domotorp
fuente

Cuando dice que "no importa cómo cortamos la entrada en dos partes", ¿su argumento también descarta reducciones cuando la permutación se divide en más de dos partes? Por ejemplo, en el documento vinculado sobre el recuento del número de inversiones, hay una reducción de la disyunción establecida, donde Alice y Bob tienen entradas

, y forman permutaciones

. El índice 0 o 1 se refiere a las transformaciones

A, B \subseteq [n]

$A, B \subseteq [n]$

\bar{A_{0}} B_{1} A_{0} \bar{B_{1}}

$\bar{A_0} B_1 A_0 \bar{B_1}$

\bar{A_{1}} B_{0} A_{1} \bar{B_{0}}

$\bar{A_1} B_0 A_1 \bar{B_0}$

2 x

$2x$ y

, y la barra se refiere a complementar. En otras palabras, ¿qué pasa si la comunicación puede ser multi-ronda?

2 x + 1

$2x+1$

László Kozma

@laszlo: en este problema, realmente no importa cómo se corta la entrada siempre que se la dé a dos jugadores, ya que la paridad de la permutación está determinada por el número de sus ciclos (por lo que es por eso que difiere del número de inversiones).

domotorp

¿Es fácil ver cómo A puede calcular un bit a partir de su entrada usando qué B puede calcular la paridad? Veo cómo A y B saben el número de ciclos "dentro de sus partes". Pero, ¿cómo encuentran la paridad del número de ciclos de "cruce"?

László Kozma

@laszlo: supongamos que la entrada de A es algo así como 1-> 7, 2-> 5, 3-> 8, 4-> 6. Tiene el mismo número de inversiones que 1-> 5, 2-> 6, 3-> 8, 4-> 7. De manera más general, B sabe en qué números se asignan los números de A. Usando un número par de inversiones, A puede permutar estos números en un orden creciente, excepto posiblemente para los dos últimos. La relación de estos dos últimos números es el bit que ella envía.

domotorp

a_{1}, \dots, a_{n}

$a_1, \dots, a_n$

a_{n + 1}, \dots, a_{2 n}

$a_{n+1}, \dots, a_{2n}$

a_{2 n + 1}, \dots, a_{3 n}

$a_{2n+1}, \dots, a_{3n}$

a

$a$

[3 n]

$[3n]$

o (n)

$o(n)$