-completitud de reconocer la diferencia de dos permutaciones

Shor declaró, en su comentario a la respuesta anónima de los alces a esta pregunta ¿Puedes identificar la suma de dos permutaciones en el tiempo polinómico? , que es completo para identificar la diferencia de dos permutaciones. Desafortunadamente, no veo una reducción directa del problema de la suma de permutación y es útil tener la reducción de la completitud para el problema de la diferencia de permutación. $NP$ $NP$

Diferencia de permutación:

INSTANCIA: Una matriz de enteros positivos. $A[1...n]$

PREGUNTA: ¿Existen dos permutaciones y de los enteros positivos tales que para ? $\pi$ $\sigma$ $1,2, ... , n$ $|\pi(i) - \sigma(i)| = A[i]$ $1 \le i \le n$

¿Cuál es la reducción para probar la completitud de reconocer la diferencia de dos permutaciones? $NP$

EDITAR 10-9-2014 : el comentario de Shor da una reducción que prueba la completitud cuando los elementos de la secuencia son diferencias con signo . Sin embargo, no veo una reducción fácil a mi problema donde todos los elementos de son los valores absolutos de las diferencias. $NP$ $A$ $A$

ACTUALIZACIÓN: El problema de la diferencia de permutación parece ser completo, incluso si una de las dos permutaciones es siempre la permutación de identidad. La prueba de dureza de este caso especial es muy bienvenida. Por lo tanto, estoy interesado en -completitud de esta versión restringida: $NP$ $NP$

Diferencia de permutación restringida: INSTANCIA: Una matriz de enteros positivos. $A[1...n]$

~~Pregunta: ¿existe una permutación de los enteros positivos tal que para ? $\pi$ $1,2, ... , n$ $|\pi(i) - i| = A[i]$ $1 \le i \le n$~~

Actualización 2 : El problema restringido es eficientemente decidible como se muestra en la respuesta de mjqxxxx. La complejidad computacional del problema original no está probada.

EDITAR 9/6/16 : Estoy interesado en determinar si esta simplificación de la diferencia de permutación es NP-completa:

Diferencia de permutación restringida:

INSTANCIA : Un conjunto múltiple de enteros positivos. $A$

PREGUNTA : ¿existe una permutación de los enteros positivos tal que ? $\pi$ $1,2, ... , n$ $A= \{|\pi(i) - i| :1 \le i \le n\}$

cc.complexity-theory co.combinatorics np-hardness permutations Mohammad Al-Turkistany
fuente

¿Por qué no preguntarle a Peter directamente? @Peter

caozhu

¿Quieres decir por correo electrónico? Lo haré.

Mohammad Al-Turkistany

Puede que me falte algo, pero ¿no puede representarse este problema como un 2-SAT y, por lo tanto, resolverse en polytime? Podemos suponer WLOG que una de las permutaciones es la identidad (supongo que A [i] se calcula cíclicamente; ¿eso debería importar mucho?), Y luego podemos representar la segunda por una matriz

. Ser una matriz de permutación es una conjunción de las cláusulas de dos variables que indican que no hay dos en una fila o en una columna; y luego decir que la diferencia está en las ubicaciones de pi (i) de i es A [i] es el OR de los dos lugares posibles en los que puede estar.

x [i, j]

$x[i,j]$

Noam

@Noam Gracias por tu comentario. Idea interesante. No lo pensé. Sin embargo, no es obvio para mí si conducirá a un algoritmo de tiempo polinómico, especialmente porque solo se nos da el valor absoluto de las diferencias.

Mohammad Al-Turkistany

Sí, parece que la diferencia entre contar la brecha cíclicamente o en valor absoluto puede ser importante.

Noam

Respuestas:

El problema restringido, donde una de las permutaciones es la identidad, es ciertamente en . Construya el gráfico bipartito donde cada vértice está conectado al elemento (s) tal que . Entonces la permutación deseada $\mathsf{P}$ $i \in V_1=\{1,2,\ldots,n\}$ $j \in V_2=\{1,2,\ldots,n\}$ $|i-j|=A[i]$ $\sigma$ existe si y solo si el gráfico tiene una coincidencia perfecta (es decir, una coincidencia con aristas), que puede determinarse en tiempo polinómico. $n$

mjqxxxx
fuente

Puede que me falte algo, pero cualquier combinación perfecta no funcionará. Debes demostrar la existencia de una combinación perfecta restringida. Considere un número entero

que aparece dos veces en la matriz de entrada

. La coincidencia perfecta que corresponde a la permutación debe tener dos aristas con diferencia absoluta

. Su algoritmo NO prueba la existencia de dicha coincidencia restringida. Esto es lo que hace que el problema sea difícil y posiblemente NP-completo.

k

$k$

A

$A$

k

$k$

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Creo que si

entonces

están vinculados a los nodos

A [i] = A [j] = k

$A[i] = A[j] = k$

u_{i}, u_{j} \in V_{1}

$u_i, u_j \in V_1$

v_{i + A [i]}, v_{i - A [i]}, v_{j + A [j]}, v_{j - A [j]} \in V_{2}

$v_{i+A[i]},v_{i-A[i]},v_{j+A[j]},v_{j-A[j]} \in V_2$ con diferencias absolutas

. La coincidencia perfecta incluirá al menos un borde de

y un borde de

. Llegué a la misma conclusión hace algunas veces mientras pensaba en el problema original, pero de otra manera: vi que es fácil formular el problema restringido como una fórmula 2-SAT (si lo desea, puedo agregar una respuesta con él) , pero la idea de mjqxxxx es mejor).

k

$k$

u_{i}

$u_i$

u_{j}

$u_j$

Marzio De Biasi

@MarzioDeBiasi ¿Por qué este enfoque (y el suyo) no funciona para el problema original (sin restricciones)?

Mohammad Al-Turkistany

@mjqxxx Veo que su enfoque resuelve el caso restringido. ¿Por qué no se puede extender para resolver eficientemente el problema original?

Mohammad Al-Turkistany

i

$i$

δ_{i} (n) \to (π_{i} (n + A [i]) \lor π_{i} (n - A [i]))

$\delta_i(n) \to (\pi_i(n+A[i]) \lor \pi_i(n-A[i]))$

$\{1,2,3,\ldots,n\}$ $\{1,2,4,8,\ldots\}$ $\pi$ $A = \{|\pi(2^k) - 2^k| : 2^k \in \Omega\}$ $\Omega$ $A$ $2^{k_1}-2^{k_2}$ $k_1,k_2$ $k_1\ne k_2$ $k_1$ $k_2$ $|2^{k_1} - 2^{k_2}|$ $A$ $\pi(2^{k_1}) = 2^{k_2}$ $\pi(2^{k_2}) = 2^{k_1}$

$G = (L \sqcup R, E)$ $L$ $R$ $(2^{k_1},2^{k_2})$ $(2^{k_2},2^{k_1})$ $|2^{k_1} - 2^{k_2}|$ $A$ $k_1 \ne k_2$

$\pi$ $A$
$G$

$1 \implies 2$ $2 \implies 1$ $G$ $L$ $R$ $G$ $G$ $\pi$ $L$ $R$

Puede formular el algoritmo anterior como una pregunta de coincidencia perfecta, e imagino que hay otras reducciones a 2-SAT. Sin embargo, no veo cómo extender estos enfoques al problema original.

Andrew Morgan
fuente