Você consegue identificar a soma de duas permutações no tempo polinomial?

29

Recentemente, houve duas perguntas feitas no cs.se que estavam relacionadas ou tiveram um caso especial equivalente à seguinte pergunta:

Suponha que você tenha uma sequência de números tais que Decomponha-o na soma de duas permutações, e , de , de modo que ,. n n i = 1 a i = n ( n + 1 ) . π σ 1 n a i = π i + σ ia1,a2,anni=1nai=n(n+1).πσ1nai=πi+σi

Existem algumas condições necessárias: se o estiver classificado de forma que devemos tera 1a 2a naia1a2an

i=1kaik(k+1).

No entanto, essas condições não são suficientes. Da resposta a esta pergunta de math.se que fiz, a sequência 5,5,5,9,9,9 não pode ser decomposta como a soma de duas permutações (pode-se ver isso usando o fato de que 1 ou 5 só podem ser emparelhado com 4).

Então, minha pergunta é: qual é a complexidade desse problema?

Peter Shor
fonte
Aliás, uma variação simples veio à minha mente e não tenho certeza sobre sua complexidade. Você consegue identificar a soma livre de ponto fixo de duas permutações no tempo polinomial? (É necessário que as duas permutações discordam em cada posição ie para todos ) iπiσii
Mohammad Al-Turkistany

Respostas:

20

Não, você não pode identificar a soma de duas permutações no tempo polinomial, a menos que P = NP. Seu problema é NP-completo, pois a versão de decisão do seu problema é equivalente ao problema NP-completo - Correspondência Numérica com somas de destino:2

Entrada: Sequência de de números inteiros positivos, , paran i = 1 a i = n ( n + 1 ) 1 a i2 n 1 i na1,a2,ani=1nai=n(n+1)1ai2n1in

Pergunta: Existem duas permutações e tais que para ?ψ 2 ψ 1 ( i ) + ψ 2 ( i ) = a i 1 i nψ1ψ2ψ1(i)+ψ2(i)=ai1in

Na referência, uma variante severamente restrita de NUMERICAL 3-DIMENSIONAL MATCHING (RN3DM) demonstrou ser fortemente NP-completa.

RN3DM, Dado um multiset de números inteiros e um número inteiro tal que , existem duas permutações e tais que , para ?e Σ n j = 1 u j + n ( n + 1 ) = N e λ μ u j + λ ( j ) + μ ( j ) = e j = 1 , . . . , nU={u1,...,un}ej=1nuj+n(n+1)=neλμuj+λ(j)+μ(j)=ej=1,...,n

Há uma redução fácil de RN3DM para Correspondência Numérica com problema de somas de destino: Dada uma instância de RN3DM. Construímos a instância correspondente criando paraa i = e - u i 1 i n2ai=eui1in

W. Yu, H. Hoogeveen e JK Lenstra. Minimizar a produção em uma loja de fluxo de duas máquinas com atrasos e operações de unidade de tempo é difícil para NP . Journal of Scheduling, 7: 333–348, 2004

EDITAR 1º de outubro : Seu problema é chamado Soma de Permissão. Está listado desde 1998 em OPEN PROBLEMS IN COMBINATORIAL OPTIMIZATION por Steve Hedetniemi.

Mohammad Al-Turkistany
fonte
2
Obrigado pela resposta. Eu respondi a um dos problemas no cs.se que inspirou esse (que não estava em um formulário respondido diretamente por sua referência), mas acho que você deve ter a primeira chance de responder ao segundo, já que a resposta é dada em sua referência.
precisa
Muito obrigado Peter. Fico feliz por poder ajudá-lo. Eu acho que você produzirá uma resposta melhor. Então, por favor, vá em frente e responda a essa pergunta também.
Mohammad Al-Turkistany
Aqui está a declaração do problema, como apareceu na página da Web acima: SUMOS DE PERMUTAÇÃO [Cheston, 198X] INSTANCE: Uma matriz A [1..n] de números inteiros positivos. PERGUNTA: Existem duas permutações r e s dos números inteiros positivos {1,2, ..., n} tais que para 1 <= i <= n, r (i) + s (i) = A [i] ?
Mohammad Al-Turkistany
4

Por outro lado, Marshall Hall mostrou que é possível identificar facilmente a diferença de duas permutações.

alce anônimo
fonte
14
nZ
3
@ PeterShor Para completar, publique seu comentário como resposta separada, fornecendo um esboço de prova da completude do NP para identificar a diferença de duas permutações.
Mohammad Al-Turkistany
3
ϕππ¯(i)=n+1π(i)ϕ+π{x1,x2,,xn}ϕπ¯{x1(n+1),x2(n+1),,xn(n+1)}{2,2,2,2,2,2}{5,5,5,9,9,9}
315 Peter Peter Shor