Recientemente se hicieron dos preguntas en cs.se que estaban relacionadas o tenían un caso especial equivalente a la siguiente pregunta:
Suponga que tiene una secuencia de números tales que Descomponerlo en la suma de dos permutaciones, y , de , de modo que . n ∑ n i = 1 a i = n ( n + 1 ) . π σ 1 … n a i = π i + σ i
Hay algunas condiciones necesarias: si se ordena de modo que , entonces debemos tenera 1 ≤ a 2 ≤ … ≤ a n
Sin embargo, estas condiciones no son suficientes. De la respuesta a esta pregunta matemática que hice, la secuencia 5,5,5,9,9,9 no se puede descomponer como la suma de dos permutaciones (se puede ver esto usando el hecho de que 1 o 5 solo pueden ser emparejado con 4).
Entonces mi pregunta es: ¿cuál es la complejidad de este problema?
Respuestas:
No, no puede identificar la suma de dos permutaciones en el tiempo polinomial a menos que P = NP. Su problema es NP-complete ya que la versión de decisión de su problema es equivalente al problema NP-complete - Coincidencia numérica con sumas objetivo:2
Entrada: Secuencia de de enteros positivos, ∑ n i = 1 a i = n ( n + 1 ) , 1 ≤ a i ≤ 2 n para 1 ≤ i ≤ nuna1, una2, ... anorte ∑nortei = 1unayo= n ( n + 1 ) 1 ≤ ayo≤ 2 n 1 ≤ i ≤ n
Pregunta: ¿Hay dos permutaciones y ψ 2 tales que ψ 1 ( i ) + ψ 2 ( i ) = a i para 1 ≤ i ≤ n ?ψ1 ψ2 ψ1( i ) + ψ2( i ) = ayo 1 ≤ i ≤ n
En la referencia, se demostró que una variante severamente restringida de NUMERICAL 3-DIMENSIONAL MATCHING (RN3DM) era NP-completa.
Hay una reducción fácil de RN3DM a Problema de coincidencia numérica con sumas objetivo: dada una instancia de RN3DM. Construimos la instancia correspondiente haciendo un i = e - u i para 1 ≤ i ≤ n2 unayo= e - uyo 1 ≤ i ≤ n
W. Yu, H. Hoogeveen y JK Lenstra. Minimizar la fabricación temporal en un taller de flujo de dos máquinas con retrasos y operaciones por unidad de tiempo es muy difícil . Journal of Scheduling, 7: 333–348, 2004
EDITAR 1 de octubre : su problema se llama SUMAS DE PERMUTACIÓN. Está en la lista desde 1998 en PROBLEMAS ABIERTOS EN OPTIMIZACIÓN COMBINATORIA por Steve Hedetniemi.
fuente
Por otro lado, Marshall Hall demostró que es posible identificar fácilmente la diferencia de dos permutaciones.
fuente